2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Frango Fuentes Nov 4 at 0:14
0
$\begingroup$

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.

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

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.