Recurrence relation tree method tight bound-CodePudding

I am trying to find the asymptotic tight bound for this recurrence: T(n) = T(n/2) T(2n/4) n

I am utilizing the recursive tree method to do so, but I am lost towards the end and would appreciate any guidance.

T(n/2) = T(n/4) T(n/4) n/2

T(2n/4) = T(n/2) so it's also T(n/4) T(n/4) n/2

T(n/4) = T(n/8) T(n/8) n/4

tree:

T(n/2) and T(2n/4)

T(n/4) and T(n/4) and T(n/4) and T(n/4)

until T(1) for all of them

At level 1, there is 1 recurrence. At level 2, there is 1 recurrence. The cost at the root is n. The cost at level 1 is n. The cost at level 2 is n.

I know the depth = n/(2^k) = 1 so k = logbase2(n).

However, I am confused about what to do after this. How would I continue going about this problem to find its tight bound?

CodePudding user response：

You have all of the pieces, it's just about understanding the recursion-tree method. To find the total cost, you sum the costs of each node (subproblem) across each level of the tree to get per-level costs, then sum the per-level costs to get the total cost.

You've found that the cost at each level is always n, since the number of nodes at depth i, for i in 0, 1, ... k is 2^i. At depth i, the cost of each node is n/(2^i) * T(1) as you say. So, since k = log2(n) - 1 is the maximum depth, we get a sum over i in 0, 1, ... log2(n) - 1 of n.

This gives a total of (n log2 n) * T(1), and since T(1) is a constant in ϴ(1), we get T(n) ∈ ϴ(n log2 n). This is usually written as ϴ (n log n) without specifying a base, since log2 x ~ log10 x ~ ln x are separated by a constant multiple, and asymptotically equivalent to any other logarithm with a base greater than 1.