1
$\begingroup$

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

enter image description here

2.)

enter image description here

$\endgroup$
5
$\begingroup$

It's quite easy, you just have to write down the first terms :

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

$\endgroup$
  • $\begingroup$ This makes a lot of sense. For problem 1, the upper bound is logarithmic because each time, the iteration in the inner loop is decreasing by 1/2. One question one though, why is the final Order O(n)? Is it because this problem is closer to 1.5 loops rather than 2, because it is continuously speeding up? $\endgroup$ – user10304 Sep 23 '13 at 22:48
  • $\begingroup$ Actually now that i think about it, I don't understand how you establish the order of complexity of either of these problems. I understand the summation equation, just not how it translates into the final answer of O(n) and O(n^2) $\endgroup$ – user10304 Sep 24 '13 at 0:24
  • $\begingroup$ I added some details and corrected the $O(n^2)$ into $O(n \log n)$ since the sum is the harmonic serie. $\endgroup$ – Tpecatte Sep 24 '13 at 8:54
  • $\begingroup$ @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}$). $\endgroup$ – Bakuriu Sep 24 '13 at 12:24
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.