Having trouble understanding O-notation. This is the question:
10. The approximate number of iterations of an algorithm with data size N is determined to be: 1 + 2 + 3 + ... + N
a. Write a table that shows N and the number of iterations for the first 10 values of N.
b. What is the O-notation for this algorithm?
I think the O-notation is O(N) but I am not sure. Any help would be appreciated. Thanks.
It is O(N*N)
[tex]1+2+3+...+N[/tex]
= [tex]N*(N+1)\over 2[/tex] Geometrical Series Addition
= [tex] {N^2 \over 2} + {N \over 2}[/tex]
[tex]\lim_{N\to\infty}{N^2 \over 2} + {N \over 2} = N^2[/tex]
So it is [tex]O(N^2)[/tex]
[tex]\lim_{N\to\infty}{N^2 \over 2} + {N \over 2} = N^2[/tex]
Don't use fake mathematics. For starters, N^2/2 is nowhere near N^2. And even if you wrote N^2/2, the distance away as N appoaches infinity would be infinity also.
The reason the function is [tex]O(N^2)[/tex] is that, with [tex]N_0 = 5[/tex] and [tex]k = 1[/tex], it's true that [tex]\frac{N^2}2 + \frac{N}2 \leq k N^2[/tex], for all [tex]N \geq N_0[/tex]. Other values would work for [tex]N_0[/tex] and [tex]k[/tex], too.
Your intuition is correct, of course; it would be correct to say that
[tex]\lim_{N\to\infty}\frac{\frac{N^2}2 + \frac{N}2}{N^2} = \frac12[/tex]. And that is also sufficient to prove big-O-ness (since that proves the previous statement).
Don't use fake mathematics. For starters, N^2/2 is nowhere near N^2. And even if you wrote N^2/2, the distance away as N appoaches infinity would be infinity also.
[tex]\frac{N^2}2 + \frac{N}2 \leq k N^2[/tex], for all [tex]N \geq N_0[/tex],
where in this particular case, [tex]N_0 = 5[/tex] and [tex]k = 1[/tex] are satisfying values (but of course others work).That is why the function is [tex]O(N^2)[/tex].
Your intuition is correct, of course; it would be correct to say that
[tex]\lim_{N\to\infty}\frac{\frac{N^2}2 + \frac{N}2}{N^2} = \frac12[/tex]. And that is also sufficient to prove big-O-ness.
I know that [tex]N^2[/tex] is nowhere equal to [tex]{N^2} \over 2[/tex]
But I thought since both[tex] N^2[/tex] and [tex]{N^2} \over 2[/tex]is going to infinity what the hell. Infact I thought there was a theorem to that effect.:cheesy: Anyway no excuses. It has been 10 years since my last calculus lecture. Don't feel like brushing up either. You should be correct, since you are more in touch than I am.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.