1
$\begingroup$

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?

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Use the Akra-Bazzi theorem. $\endgroup$ – Yuval Filmus Aug 28 '17 at 11:00
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It can't be less than $\Omega(n)$ because there is already $n$ work being done at the highest level. $\endgroup$ – ryan Aug 28 '17 at 1:28
  • $\begingroup$ 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. $\endgroup$ – someone12321 Aug 28 '17 at 14:53
  • $\begingroup$ 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)$. $\endgroup$ – ryan Aug 28 '17 at 15:46
  • $\begingroup$ Thanks for your explanation, I didn't get the different between recurrence relation and function, should I remove my answer from this post? $\endgroup$ – someone12321 Aug 28 '17 at 16:11

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