Master's theorem

Question

Can master's theorem be applied if b=1? Or strictly when b>1?

Comments

i think  It Not Possible Divided By Zero Is Infinite Not Get Any Complexity 

It Must Be Strictly  b>1 All remaining Are > or = 0 like A>=0,k>=0, Yes ?

Correct Me Iam Wrong ?

Answer 1

Master's theorem

Comments

I think it should be strictly greater then 1....because with respect to time the remaining input must decrese.

---

yes ,b should be strictly greater than 1..Master theorem is generally applicable for Divide and Conquer algorithms...We get the better running time in these algorithms generally because we divide the original problem of size 'n' into n/2 ,n/3... rather than n-1 , n-2,...So, Recurrence Relation should be T(n) = aT(n/b) + f(n) , here a = number of subproblems , n/b = size of each subproblem and f(n) is the work to combine subproblems...So ,if b=1 then it means we didn't break the original problem ..So ,b=1 is not possible and also 'a' should be constant...

Answer 2

b = 1 , Doesn't makes sense.

T(n) = T(n) + f(n) ,

Did you get what this recurrence relation is doing?

T(n) in each step doesn't divide or reduce the problem size. This will lead to infinite loop.

When b > 1

T(n) = T(n/2) + c

Problems size is reduced at each step here.

Hopefully you got it.

Comments

Thanks brother