Question

how to find complexity of an algorithm based on recurrence relation?

Answer 1

By Master Theorem :-

It's often possible to compute the time complexity of a recursive function by formulating and solving a recurrence relation.

Master theorem

T(n) = Θ(nd) if a < bd,

T(n) = Θ(ndlog n) if a = bd,

T(n) = Θ(nlogba) if a > bd.

Answer 2

By Master Theorem:

It's often possible to compute the time complexity of a recursive function by formulating and solving a recurrence relation.

Master Theorem

T(n)= (nd) if a <bd,

T(n)= (ndlog n) if a=bd

T(n)= (nlogba) if a>bd.