# What is the algorithm complexity in Big-Theta notation?

I need to find the complexity of Code(n) algorithm in terms of Big Theta notation. Thank you in advance.

Code(n)

1. i=n
2. while i>1 do
3.    j=i
4.    while j<n do
5.        k=0
6.        while k<n do
7.            k=k+2
8.        j=2*j
9.    i=i/2

The approach I made is the following:

Supposing line (2) is run $$t$$ times, then line (4) is run $$\sum_{i=0}^{t-1}{i}$$ times if $$n>2$$ and $$0$$ times if $$n\leq 2$$.

$$\dfrac{t(t-1)}{4}\cdot n$$ is the amount of times line (7) is run when $$n>2$$ ($$0$$ times otherwise).

I need help finding the upper and lower bound so I can find the complexity in Theta notation.

The innermost loop runs $$\lfloor\frac n2\rfloor$$ times. The middle loop runs $$\lfloor \log_2(n/i)\rfloor$$ where $$i$$ varies in a geometric progression of common ratio $$2$$ (hence the number of iterations decreases linearly) and the outer loop runs $$\lfloor \log_2(n)\rfloor$$ times.

Globally,

$$\frac12\lfloor \log_2(n)\rfloor(\lfloor \log_2(n)\rfloor+1)\left\lfloor\frac n2\right\rfloor$$ executions of the body, which is $$\Theta(n\log^2(n))$$.

• How did you get that the innermost loop runs $\lfloor\dfrac{n}{2}\rfloor$? If $n=3$, by following the logic of the code, I get that the innermost loop is entered $2$ times. – Frango Fuentes Nov 4 at 0:14

Writing the loops as a sum is key to determine the algorithmic complexity. In your case the boundaries

$$\sum_{i=1}^{\log n} \sum_{j=i}^{\log n/i} \sum_{k=0}^{n/2} 1$$

Note that your most inner loop actually adds even numbers. Therefore, for simplifying the calculations, you can use formulas.

• There is a typo in your formula. – Yves Daoust Oct 29 at 8:27