textbook

Question

T(n)=T(7n/8)+0.05

solve this equation and find out the time complexity?

Comments

logn base 8/7.==Olog(n) is it the ans??

Answer 1

$\large T(n)=T(\frac{7n}{8})+0.05$

$\large T(n)=T(\frac{n}{\frac{8}{7}})+0.05$

$\large T(n)=T(\frac{n}{(\frac{8}{7})^{2}})+0.05+0.05$

$\large T(n)=T(\frac{n}{(\frac{8}{7})^{3}})+0.05+0.05+0.05$

After substituting k time ,

$\large T(n)=T(\frac{n}{(\frac{8}{7})^{k}})+k*0.05$

Now Let,

$\LARGE \frac{n}{(\frac{8}{7})^{k}}=1$

$\large n=(\frac{8}{7})^{k}$

taking $log$ with base $\large \frac{8}{7}$,

$\large k=\log_{\frac{8}{7}}n$

Now as we con

$\large T(n)=T(1)+k*0.05$

$\large T(n)=T(1)+\log_{\frac{8}{7}}n *0.05$

As nothing is mentioned Let $\large T(1)=c$,

$\large T(n)=c+\log_{\frac{8}{7}}n*0.05$

So, Time complexity is $\large \Theta (logn)$

Answer 2

A = 1 , B=8/7 , apply masters theorem.

Comments

We can not apply master's theorem .

T(n)=aT(n/b)+f(n) standard form of master's theorem ,

According to questions f(n) is constant not a function of n so we can not apply master's theorem .

It questions solve by recursive tree method .

If I am correct its ans is O(logn).