Madeeasy Algorithm

Question

How to solve this recurrence relation

T(n)= T(0.09n) + T(0.91n) + cn

where c is constant and T(1)=1

options are-

Comments

Re write the equation as

T(n)=T(9n/100)+T(91n/100) +n

 and solve

---

---

@Kabir5454

Edit: Rotated the beautiful answer.

---

@Kabir5454 I understand till height of right side tree and left side tree. not able to get last three lines of your solution please explain..

---

@Shreya2002 before explaining that can you tell me which side of the tree has more height ? Or both side have same height for the tree ?

For this recurrence relation

T(n)=2T(n/2)+n which side of the tree has more height?

---

@Abhrajyoti00 i think B is also a possible answer ?

what do you think ?

---

@Kabir5454 The right subtree has more height as you can see in my answer. Hence only Option A is correct.

---

Right sub-tree has more height which is $\log_{0.91}\frac{1}{n}$  .and work done in each level in $n$ . which implies  $T(n)=O(nlog_{0.91}\frac{1}{n})$ .

left sub-tree has less height which is $\log_{0.09}\frac{1}{n}$  .and work done in each level in $n$ . which implies  $T(n)=\Omega(nlog_{0.09}\frac{1}{n})$ .

Now if we want to calculate the T(n) in terms of $\Theta$ notation the base was not matter as we convert the base by multiplying some constant .

So, we can write ,

$n\log_{0.09}\frac{1}{n}\leq T(n)\leq n\log_{0.91}\frac{1}{n}$

---

If you argue with the greater height then the answer should be given in $big -oh$ notation not in $\Theta$ .

---

@Kabir5454 Most of the time it has a cost of $ n\log_{0.91}\frac{1}{n}$. Hence we use $\Theta$ notation for answering time complexity qs. Moreover you can notice all equations of Master Theorem in CLRS has used $\Theta$ notation. 

We shouldn’t say $\Theta( n\log_{0.09}\frac{1}{n})$ because it is very negligible compared to the other one. So if someone asks for time complexity of such q, why should we say that average is the lesser one (nearly negligible)? 

---

@Abhrajyoti00 Most of the times – even 99% of the time does not matter for proofs. It must be 100%. Can you point to an example in CLRS where $\Theta$ notation is used in place of $O$ without actually proving the lower bound?

---

@Kabir5454 max(log0.09 (n), log0.91 (n)) = log0.09 (n) right?

---

@gatecse Sir, thanks for the reply. Yes definitely CLRS uses $\Theta$ after proving both the bounds, but for qs of Divide and Conquer mostly they use Master’s Theorem and answer it in terms of $\Theta$. 

I also agree that for this question $O$ should have been better option, but using theta to say the lower value doesn’t feel appropriate. 

---

@Shreya2002

You can think it like you are diving the n by factor of (100/9) and (100/91).

So by dividing and extending the tree to base at the end it should reach to base case. There $\frac{n}{(\frac{100}{9})^{k} }=1$

Another side ,

$\frac{n}{(\frac{100}{91})^{k} }=1$

So the denominator (100/91) in $\frac{n}{(\frac{100}{91})^{k} }$ is small with respect to (100/9) . So the height of the right side having denominator (100/91) has more height and (100/9) has less height.

So, the lower bound for T(n) would correspond for the lower height and upper bound correspond to higher height.

That is what I have written in last three line.

$T(n)=\Omega (n\log_{\frac{100}{9}}n)=\Omega(n\log_{0.09}\frac{1}{n})$

$T(n)=O(n\log_{\frac{100}{91}}n)=O(n\log_{0.91}\frac{1}{n})$

---

@Kabir5454 Whatever you’ve said is correct. What I’m saying is w.r.t this q, Option A seems more appropriate than Option B.

---

@Abhrajyoti00 When $\Theta$ is applicable we always use that as it is more stricter. Now coming to this question the job is to prove option B false (if it is false). There is no easy way out.

---

@Kabir5454 so have you proved $\Theta$ part?

---

bro say if there is 10^9 possibilities for a problem for which 10^9-1 goes in favor of option A and 1 case goes in favor of option B , then we must say both possible . There is nothing appropriate if it is correct it is correct in term of proof I am saying and don’t waste your instinct based on made easy question there are more wrong answer that correct in test series .

---

@Kabir5454 When does base of logarithm matter for asymptotic notations?

---

@gatecse here it doesn’t matter as if we change the base it will be same as multiplying by some factor but in case of 

$4^{\log_{4}n}=n$ but if we change the base to 16 then ,$4^{\log_{16}n}=\sqrt{n}$ so base matter in these scenario .

---

yes. So now you have proved $\Theta$ part right?

---

Lets do it formally ,

as already explained $T(n)=\Omega (n\log_{\frac{100}{9}}n)$=$\Omega (n.\frac{\log_{a}n}{\log_{a}\frac{100}{9}})$=$\Omega (n.\log_{a}n)$ [ a is some constant base]

$T(n)=O (n.\log_{\frac{100}{91}}n)=O(n.\frac{\log_{a}n}{\log_{a}\frac{100}{91}})=O(n\log_{a}n)$.

So,we know ,

$T(n)=\Theta(f(n))$ if and only if $T(n)=\Omega(f(n))$ and $T(n)=O(f(n))$ .

So we can conclude ,$T(n)=\Theta(n \log_{a}n)$ .

This also proof option (B) is true .if we put $a=100/9$ .

---

yes, that’s it. Suppose this is a MCQ in GATE (or any other standard exam) both options A and B will get full marks. Suppose it is a MSQ, only “A;B” will get mark. There is no ambiguity over it.

---

Correct sir.

---

Thanks @Kabir5454 and @gatecse Sir for pointing out my mistake.

P.S. I have corrected the answer accordingly attaching @Kabir5454 ‘s proof (not sure if I am authorized to copy someone’s comment and put on my own answer after giving his/her credit).

---

You’re welcome @Abhrajyoti00

Of course it depends on the person but no reasonable person will object to sharing his/her education content when due credit is mentioned unless there is a legal restriction (like content being owned by some company).

Also knowledge is supposed to be shared. If you read and understand something, you can always share it in your own words and no copyright applies. 

Answer 1

Answer: Both Option A and Option B.

The total cost becomes = $n.log_{0.91}(1/n)$.

Now we can say : $n\log_{0.09}\frac{1}{n}\leq T(n)\leq n\log_{0.91}\frac{1}{n}$

Thus, $O(n.log_{0.91}(1/n))$ and  $\Omega(nlog_{0.09}\frac{1}{n})$

-------------------------------------------------------------------------------------------------------------------------------------------------

Attaching the proof by @Kabir5454 for $\Theta(n.log_{0.91}(1/n))$ or $\Theta(n.log_{0.09}(1/n))$:-

Lets do it formally ,

as already explained $\Omega (n.\frac{\log_{a}n}{\log_{a}\frac{100}{9}})$[ a is some constant base]

$T(n)=O (n.\log_{\frac{100}{91}}n)=O(n.\frac{\log_{a}n}{\log_{a}\frac{100}{91}})=O(n\log_{a}n)$

So,we know ,

$T(n)=Θ(f(n))$ if and only if $T(n)=Ω(f(n)) $ and $T(n)=O(f(n))$ .

So we can conclude ,$T(n)=\Theta(n \log_{a}n).$

This also proof option (B) is true .if we put $a=100/9 .$

 

Comments

Perfect answer👍

So the whole problem was because of $\Theta$ notation  .

just had some doubts here

1. if $option$ $A$ is   $\Theta(nlog_{0.91}(1/n))$  And $option$ $B$ is  $\Omega (nlog_{0.09}(1/n))$
2. if $option$ $A$ is   $O$$(nlog_{0.91}(1/n))$  And $option$ $B$ is  $\Omega (nlog_{0.09}(1/n))$
3. if $option$ $A$ is   $O$$(nlog_{0.91}(1/n))$  And  $option$ $B$ is  $\Theta (nlog_{0.09}(1/n))$

In all the three cases ,  both  $option$ $A$  And  $option$ $B$  are correct right?

---

Yes @Pranavpurkar all of them have both option A and B correct as proved by @Kabir5454

---

Abhrajyoti00

Thanks buddy:)