# How to represent a recurrence that increments by one at each tree level?

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

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

• 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. Commented Apr 28, 2020 at 22:59
• @Matthew it's a different qestion.
– OmG
Commented Apr 28, 2020 at 23:00