What is the algorithm complexity in Big-Theta notation?

Question

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.

Answer 1

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

Answer 2

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.