I am using a merge sort like algorithm. Each level of the tree has a different Big O runtime. The runtime as a whole can be represent as follows:

$$O(\sum_{i=0}^{log(n)}2^{\frac{n}{2^i}} * 2^i)$$

I am trying to find the recurrence. Since this is like merge sort we can start with the classic 2T(n/2). However, I am unsure how to write what comes after 2T(n/2) in the recurrence below: $$T(n) = 2T(n/2) + O(2^{\frac{n}{2^i}} * 2^i)$$ i++ each recurrence

I am aware that this is exponential time. My assumption is that this all simplifies to O(2^n). Is that assumption correct?

Bogo Sort + Merge Sort Example


1 Answer 1


As each time $n$ is divided by $2$ and $2$ multiplied by 2, it should be: $$ T(n) = 2T(\frac{n}{2}) + 2^n $$ Now, if you expand it:

$$ T(n) = 2(T(\frac{n}{2^2}) + 2^{\frac{n}{2}}) + 2^n = 2T(\frac{n}{2^2}) + 2 \times 2^{\frac{n}{2}} + 2^n $$

How can we guess $T(\frac{n}{2})$? Because $i$ is changing from $0$ to $\log{n}$. If we suppose $T(0)$, when $i = 0$, it will be the not recurrent part of the equation. Hence, we found that it is $2^n$. How did we find we should multiply by $2$? Because each time the relation is multiplied by $2$ and we have a power of it in each iteration. Hence, it should be multiplied by the recurrent part of the relation, which is $T(\frac{n}{2})$ here.

Eventually, form the mater theorem, we can conclude that $T(n) = \Theta(2^n)$.

  • $\begingroup$ Actually one mistake. It's 2^{n/2^i} +*2^i. So, n is not dived by 2 and multiple by 2. Maybe I missed something. $\endgroup$ Commented Apr 28, 2020 at 22:59
  • $\begingroup$ @Matthew it's a different qestion. $\endgroup$
    – OmG
    Commented Apr 28, 2020 at 23:00
  • $\begingroup$ @Matthew please ask it in other question. $\endgroup$
    – OmG
    Commented Apr 28, 2020 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.