What is the tightest asymptotic bound for this recurrence? [duplicate]

This question already has an answer here:

$$T(n) = T\left(\frac{n}{2}\right) + T\left(\frac{n}{4}\right) + T\left(\frac{n}{8}\right) + n$$

How do you solve this recurrence?

marked as duplicate by Yuval Filmus, David Richerby, Evil, adrianN, JuhoAug 30 '17 at 8:59

• Use the Akra-Bazzi theorem. – Yuval Filmus Aug 28 '17 at 11:00

It will be $\Theta(n)$, to save myself from rewriting an entire answer, I will refer you to this question and you can apply the answer to your question.
Because in each recurrence you are cutting $n$ by half you will have at most $log(n)$ calls, if you use memorization, memorization will make your code faster because you will avoid overlapping calls, because $T(n/4) = T(n/2/2)$.
If $n$ is small number and you can use normall array for storing the values the complexity will be $O(\log n)$, but if n is big (up to $10^{18}$) then you can optimaze by using some data structures (map in c++) to make the complexity $O((\log n)^2)$
• It can't be less than $\Omega(n)$ because there is already $n$ work being done at the highest level. – ryan Aug 28 '17 at 1:28
• I don't understand you why do we need linear complexity to solve this recurrence, for example if $n = 32$ we don't need to calculate T(31) or T(30), we can just calculate T(32), T(16), T(8), T(4), T(2), T(1), we calculate $\log N$ values so the complexity is $O(\log N)$, can you explain more clearly. – someone12321 Aug 28 '17 at 14:53
• The implicit assumption is that the recurrence represents the running time of some recursive algorithm. This is typically what recurrence relations are for. If this were simply a function, not a recurrence relation, then sure you could solve the function in less than $\Omega(n)$. – ryan Aug 28 '17 at 15:46