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$

1 Answer 1

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$
8
  • $\begingroup$ I am sorry, could you elaborate a little on your answer? I am not following your reasoning. $\endgroup$ Oct 3, 2019 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$ Oct 3, 2019 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$ Oct 3, 2019 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$ Oct 3, 2019 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$ Oct 4, 2019 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.