0

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.

4
Contributors
4
Replies
5
Views
11 Years
Discussion Span
Last Post by WolfPack
0

[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]

1

[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).

Votes + Comments
Thx for the correction
0

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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.