0
$\begingroup$

I know for a fact that algorithm A runs in $\Theta(n)$, but how does one derive that?

Algorithm A

i = 1
while i ≤ n
  s = 0
  while s ≤ i
    s = s + 1
  i = 2 ∗ i

The inner loop is clearly $O(i)$ (linear time).

The outer loop is clearly $O(\log n)$ (logarithmic time).

A visualitation of the loop in terms of an input $n$ would look as follows:

enter image description here , the black lines represents the amount of work or iterations required in terms of $n$.

$\endgroup$
2
$\begingroup$

$\sum_{i=1}^k 2^i=\Theta(2^k)$ and you have $k\approx\log n$, so the sum is $\Theta(2^{\log n})=\Theta(n)$.

$\endgroup$
  • $\begingroup$ I am sorry, could you elaborate a little on your answer? I am not following your reasoning. $\endgroup$ – Sebastian Nielsen Oct 3 at 8:40
  • $\begingroup$ Which part do you need help with? The sum is the total amount of time spent in the inner loop if the outer loop executes $k$ times. $\endgroup$ – David Richerby Oct 3 at 8:52
  • $\begingroup$ Okay, so the inner loop runs $\sum_{i=1}^{k}2^i=2+4+8+...+k$ times ... I get that. First off, that summation is equal to $2^{k+1}-1$. As far as I am concerned, $2^{k+1}-1 \neq \Theta(2^k)$. What do you have to say about that? $\endgroup$ – Sebastian Nielsen Oct 3 at 20:24
  • $\begingroup$ @SebastianNielsen I say that, for all $k\geq 0$, $1\times 2^k\leq 2^{k+1}-1 < 2\times 2^k$ so $2^{k+1}=\Theta(2^k)$. $\endgroup$ – David Richerby Oct 3 at 23:35
  • $\begingroup$ "$k$ is the total amount of time spent in the inner loop if the outer loop executes $k$ times", which is $k\approx \log n$ ... okay, so why isn't this $\log n$ the answer (the time complexity)? Why did you (this is what I assume you did) substitute $k$ in the term $2^k$ with $\log n$ to get $Theta(2^{\log n})$? You just found out how many times the inner loop executes in terms of $n$ ... why isn't this the answer ($k\approx \log n$)? $\endgroup$ – Sebastian Nielsen Oct 4 at 6:30

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.