# Measuring time complexity of algorithm

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.

• 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? – Raphael Sep 9 '13 at 10:19

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

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

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.