Big -O time complexity of an algorithm.

Question

I need to analyze this pseudo code, do_something() is O(1) and you may assume N = 2^k for some positive integer k. I will write on each line the answer I think is correct.

Set n ← N   **1**
For i ← 1 to n  **n**
  set counter ← 1  **1**
  While counter ≤ n   **logn**
    For j ← counter to 1 **Im not sure about it, maybe 2^n -1**
      do_something()  **1**
    end
    counter ← 2 * counter **1**
  end
end

Is my analysis correct? And how I translate it to big O notation?

Thank you.

Answer 1

We can rewrite $\text{counter}=2^k$ to help make the mathematical representation a little easier.

Since the counter ranges from $1$ to $n$, this is the same as saying $2^k$ ranges from $1$ to $n$, or $k$ ranges from $0$ to $\log_2(n)$.

Let $T(n)$ be the cost function for your algorithm. Then we have:

$$T(n) = \sum_{i=1}^{n}\sum_{k=0}^{\log_2(n)}\sum_{j=1}^{2^k}1$$

Simplify the innermost loop:

$$T(n) = \sum_{i=1}^{n}\sum_{k=0}^{\log_2(n)}2^k$$

At this point, note that if $S = 2^0 + 2^1 + ... + 2^{x-1} + 2^x$, then $2S = 2^1 + 2^2 + ... + 2^x + 2^{x+1}$. Then $2S-S = S$ (most of the terms cancel out) and we get the simpler representation $S = 2^{x+1} - 2^0 = 2^{x+1} - 1$. Therefore:

$$T(n) = \sum_{i=1}^{n}(2^{\log_2(n)+1} - 1)$$

Pull out the extra factor of $2$ to simplify:

$$T(n) = \sum_{i=1}^{n}(2 \cdot 2^{\log_2(n)} - 1)$$

In general, if we have $b^{\log_b(a)} = x$, then take the log of both sides to get $\log(b^{\log_b(a)}) = \log(x)$ or $\log_b(a)\log(b) = \log(x)$. Divide both sides by $\log(b)$ and we get $\log_b(a) = \log(x)/\log(b) = \log_b(x)$. Since $\log_b(a) = \log_b(x)$, we see that $a=x$.

This means $2^{\log_2(n)} = n$. Therefore:

$$T(n) = \sum_{i=1}^{n}(2n - 1) = \sum_{i=1}^{n}2n - \sum_{i=1}^{n}1 = 2n\sum_{i=1}^{n}1 - \sum_{i=1}^{n}1 = 2n^2 - n$$

Which makes $T(n) \in O(n^2)$

In practice, you don't have to mess around too much with the extra constant terms since they won't affect the asymptotic result. In other words, we could have ignored all the various $+1$'s and $-1$'s and done something like:

$$T(n) \in O\left(\sum_{i=1}^{n}\sum_{k=0}^{\log_2(n)}\sum_{j=1}^{2^k}1\right)$$

$$T(n) \in O\left(\sum_{i=1}^{n}\sum_{k=0}^{\log_2(n)}2^k\right)$$

$$T(n) \in O\left(\sum_{i=1}^{n}n\right)$$

$$T(n) \in O\left(n^2\right)$$

Answer 2

Let's rewrite the While loop slightly. You could just make it a for loop that goes:

counter = 1
for j in [1:k]
  for m in [1:counter]
    do_stuff()
  counter = 2^j

then the total amount of steps will be: $$1+2 + 2^2 + ... 2^k = 2^{k+1} -1 = 2n -1$$

Thus your code boils down to a for loop of $\mathcal{O}(n)$ steps, which nests a for loop of $\mathcal{O}(n)$ steps. Thus the total scaling would be $\mathcal{O}(n^2)$. You can check this result by introducing a dummy variable number_of_itter and replacing do_stuff() by number_of_itter = number_of_itter +1.

Then just vary the value of $k$ to see the scaling. (Use small values as it's exponential in $k$).

Note: I'm not familiar with pseudo code syntax, so make sure my code does the same as your for loop.