Measuring time complexity of algorithm

Question

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.

Answer 1

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

Answer 2

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.