#recurrence relation

Question

Determine theta bound for recurrence :

$$T(n)=T(n/2)+T(n/4)+T(n/8)+n$$

Comments

$\Theta (n) = \Omega (n) = O(n)$

---

how to solve this recuurence?

---

Draw recursion tree for this relation.

Count the total work done in each level and write alongside the level.

For example for the first level (n) - work is n

second level (n/2,n/4,n/8) - work is 7n/8

third level  - work is = 49n/64 etc..

Count upto last level. Tree would skewed. No issue btw.

For the shorter side : sum up all level work, you will get Lower Bound = n = $\Omega (n)$

For the longer side : sum up all level work, you will get Upper Bound = $O(n)$

=> $\Theta (n)$

---

$\theta(n)$

Answer 1

It's ⊝(n) because at each level lesser work has to be done. so dominating function(at starting) will be the answer.

Comments

good job..

every thing is fine .. but just one doubt .. here height should be (log₂ n) instead of (log₄ n) right . because of T(n/2)...right ??

---

yes, so, range of leaves will be lower bound = n^1/3

upper bound = n.

---

yes it should be. thanks for pointing this out.

---

In effectively this approach gets the upper bound. So, we can use $big-O$, not $big-theta$. To use $big-theta$ we must give a lower bound also.

Answer 2

Time complexity= O(n)

Answer 3

We can see least number of nodes will be created from T(n/2).

Thus T(n/2) defines lower bound of T(n)

Sum of outputs by T(n/2) = n/2+n/4+n/8+.........= n(1/2+1/4+1/8+...)

= n[1/(1-1/2)] =2n

2n<=T(n)

Similarly

maximum number of nodes will be created from T(n/8).

Thus T(n/8) defines upper bound of T(n)

Sum of outputs by T(n/8) = 7n/8+7n/8 ² +7 n/8 ³+.........= = n[1/(1-7/8)] =8n

T(n)<=8n

We conclude 2n <= T(n) <= 8n

T(n) = θ(n)

Comments

@Arjun. We are taking summation of powers of $\frac{7}{8}$ upto height $logn$. Now, $\frac{7}{8}$ is less than 1 and its higher powers will go on becoming very much less than 1. So, they will be adding just to the fraction part of the result without making substantial change. So, infinite summation helps us approximate the result.

---

@arjun. If we take T(n/2) for T(n/4) and T(n/8), it wont be correct because they have asked Theta notation and we need to be exact, right?

---

I think least number of nodes will be created by (n/8) because if n=100, n/2 >n/8. Please correct me if am wrong

Answer 4

See the pic, complete solution  is written .

Comments

2nd method.