# Are the following loops $O(n^2)$ complexity

I'm presented with two snippets of code, and I need to determine their time complexity. I'm pretty convinced that both of these are $O(n^2)$, but I'm not 100% sure

1.)

2.)

1.) The print instruction will be called $n$ times, then $n/2$ times, then $n/4$ times, etc... Finally, the number of calls to print is $\Sigma_{i=0}^{\log n} \frac{n}{2^i} = n \Sigma_{i=0}^{\log n} \frac{1}{2^i} = n \frac{1-1/2^{\log n}}{1-1/2}=\mathcal{O}(n)$.
2.) The print instruction will be called $n$ times, then $n/2$ times, then $n/3$ times, etc... Finally, the number of calls is $\Sigma_{i=1}^{n} \frac{n}{i} = n \Sigma_{i=0}^n \frac{1}{i} = \mathcal{O}(n \log n)$.
• I added some details and corrected the $O(n^2)$ into $O(n \log n)$ since the sum is the harmonic serie. Commented Sep 24, 2013 at 8:54
• @user10304 For the first case: take a cake, cut it in half and eat an half. Take the remaining half, cut it in half and eat one of these halves(i.e. a quarter of the original). Repeat the process. How much cake can you eat at most? In the second case you can the cake in half an eat half. Then you have to eat a third of the original cake, then a quarter of the original cake etc. You can easily see that in the first example you eat only a cake, while in the second you eat a certain number of cakes that increases with the number of times you eat(which happens to be $\log{n}$). Commented Sep 24, 2013 at 12:24
Yes, they're both $O(n^2)$: in both cases, the outer ($i$) and inner ($j$) loops can be executed at most $n$ times each. Timot gives better bounds in his answer but remember that $O(-)$ is just an upper bound.