recurrance relation

Question

Let T(n) be defined by T(0) = T(1) = 4 and $T(n) = T(\left \lfloor \frac{n}{2} \right \rfloor) +T(\left \lfloor \frac{n}{4} \right \rfloor) + cn$  for all integers n >=2, where c is a positive constant. What is the asymptotic growth of T(n)?

• A. $\Theta(n)$
• B. $\Theta(n \log n)$
• C. $\Theta (n^2)$
• D. $\Theta \left(n^{\log_{\frac{3}{4}}n}\right)$

Answer 1

The answer is option A.

Using Recursive Tree Method, Time Complexity comes out to be ϴ(n) because the upper bound is O(n) and the lower bound is also Ω(n)

Comments

I removed log by as (3/4)^{lg n} be written as n^lg(3/4) .

Also, I think your logic is correct regarding decreasing GP series, its value won't get higher than 1.

But if something like appear in last $$n\left ( \frac{ \left( \frac{4}{3} \right )^{log_2 n} -1}{\left( \frac{4}{3} -1\right )}\right )$$
then what will be the answer. I don't think it a decreasing GP series.

---

Consider log₂ x graph:

 https://www.desmos.com/calculator/tpk2qk0gl1

One can observe that in between the values of (0,1)  (excluding endpoints because log 0 undefined and log₂ 2 = 1 )   

log₂(3/4) = will be a negative value.  and n^log₂(3/4)  = n ^{(less than 0)}  

=> 4cn(1-n^{(less than 0)})

=> 4cn - 4cn^{(less than 1)}  //because we are adding negative value to 1 obviously  it will be less than 1.

Higher order O(n).

And for

you can think like log₂ n  < log_(4/3) n  if we change the base of log from 2 to 4/3. The overall value will be greater than original value. Now,

n*[ { (4/3)^log_4/3 n   - 1 } / {4/3 -1} ] =   n * [ {n-1} /  {4/3-1} ] which is O(n²).  //using identity x ^{log_x a} = a 

Note: It is Big Oh (n²) and not theta(n²). because we have increased the overall value such that it will never be greater than O(n²) in worst case. Or you can simply left there as it is by taking dominating terms.

PS: not good at LaTeX :P

---

Thnx. buddy. I got my mistake I Wrongly calculate log2 (3/4), yes it will be a -ve value as it is less than 1.

Also,

 think like log₂ n  < log_(4/3) n  if we change the base of log from 2 to 4/3. The overall value will be greater than original value.

is a better approach.  

Using Recursive Tree Method, Time Complexity comes out to be ϴ(n) because the upper bound is O(n) and the lower bound is also Ω(n)

This is a nice point, that I forgot. Thnx. for reminding.

PS: Don't worry, In gate we don't need to write in LATEX. 

Answer 2

Hello

Refer Akra-Bazzi Method

Here is the link:

https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method

By solving it by using Akra-Bazzi Method I got O(n)

Please comment if any thing wrong!