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

It is O(N*N)

$$1+2+3+...+N$$

= $$N*(N+1)\over 2$$ Geometrical Series Addition

= $${N^2 \over 2} + {N \over 2}$$

$$\lim_{N\to\infty}{N^2 \over 2} + {N \over 2} = N^2$$

So it is $$O(N^2)$$

$$\lim_{N\to\infty}{N^2 \over 2} + {N \over 2} = N^2$$

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 $$O(N^2)$$ is that, with $$N_0 = 5$$ and $$k = 1$$, it's true that $$\frac{N^2}2 + \frac{N}2 \leq k N^2$$, for all $$N \geq N_0$$. Other values would work for $$N_0$$ and $$k$$, too.

Your intuition is correct, of course; it would be correct to say that
$$\lim_{N\to\infty}\frac{\frac{N^2}2 + \frac{N}2}{N^2} = \frac12$$. And that is also sufficient to prove big-O-ness (since that proves the previous statement).

Thx for the correction

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.

$$\frac{N^2}2 + \frac{N}2 \leq k N^2$$, for all $$N \geq N_0$$,
where in this particular case, $$N_0 = 5$$ and $$k = 1$$ are satisfying values (but of course others work).

That is why the function is $$O(N^2)$$.

Your intuition is correct, of course; it would be correct to say that
$$\lim_{N\to\infty}\frac{\frac{N^2}2 + \frac{N}2}{N^2} = \frac12$$. And that is also sufficient to prove big-O-ness.

I know that $$N^2$$ is nowhere equal to $${N^2} \over 2$$
But I thought since both$$N^2$$ and $${N^2} \over 2$$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.