1
$\begingroup$

I was going through a past paper question but I don't have any answers to know if I'm working out the problems correctly or not.

I need to find the time complexity for:

i) repeat
      n:=n div 2;
   until n=1;

ii) for i:=1 to n do
       begin
          for j:=1 to n do
             begin
                for k:=1 to n do;
             end;
       end;

iii) repeat
        for i:=1 to n do
           begin
              for j:=1 to n do;
           end;
     n:=n div 2
     until n=1

In my opinion, the answer for (ii) is $O(\log n)$ and the answer for (ii) is $O(n^3)$ but I'm not sure about my answers. Regarding question (iii) I have no idea how to come up with a solution.

$\endgroup$
  • $\begingroup$ An "opinion" is worth nothing here. How did you get to these proposals, what is your reasoning? Futhermore, similar questions have been dealt with multiple times here, see algorithm-analysis. Have you read any of these? Have you checked out our reference questions? $\endgroup$ – Raphael Sep 9 '13 at 10:19
1
$\begingroup$

For 1, suppose that $n = 2^{m+\delta}$, where $m$ is an integer and $\delta \in [0,1)$, and compute how many iterations the loop has.

For 2, it's easy to see that it's $\Theta(n^3)$.

For 3, the "inner" loop is $\Theta(n^2)$. Now suppose that $n = 2^{m+\delta}$ and follow the same procedure as in 1. (For starters, you might want to assume that $\delta = 0$.) You will get $\Theta$ of $$ n^2 + \frac{n^2}{4} + \frac{n^2}{16} + \cdots = \Theta(n^2). $$

$\endgroup$
  • $\begingroup$ for 1, if n = 2^m, then m = log2(n) $\endgroup$ – Ravi Teja Sep 5 '13 at 9:28
1
$\begingroup$

The standard answer is as given by Yuval Filmus.

Note that the questions are slightly flawed and can be interpreted in a different way, especially if you teacher is an adept of tricky/vicious exams.

For example, for (i) the program does not terminate if $n=0$, thus the complexity is unbounded.

On the contrary, since the inner loop of (ii) is empty, any reasonable compiler will produce a compiled code running in constant time.

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