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

Question

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

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