„n = 1 T(n) ={ 8T("/2) + dn² ,n> 1
Recursive form given below Find the open form of the T n () function and write down the Big-Oh complexity.
MASTER theorem
The master theorem is utilized in calculating the time complexity of recurrence relations simply and quickly. This uses divide and conquer algorithms.
The formula for solving recurrence relations in Master's theorem of the form:
T(n) = aT(n/b) + f(n),
where,
n = size of input
a = number of subproblems
n/b = size of each subproblem. (same size assumption)
f(n) = it is the cost of the task performed outside of the recursive call,
that includes the cost of dividing the problem and merging the solutions
Here, a ≥ 1 and b > 1 are constants, and f(n) is an asymptotically positive function means that for an adequately large value of n, we have f(n) > 0.
For any recurrsive relation the time complexity is given by
T(n) = aT(n/b) + f(n)
where ϵ > 0 is a constant.
where, T(n) has the following asymptotic bounds:
T(n)= Θ(nlogb a) , If f(n)= O(nlogb a-ϵ).
T(n)= Θ(nlogb a * log n), If f(n)= Θ(nlogb a).
T(n) = Θ(f(n)), If f(n) = Ω(nlogb a-ϵ).
Substitution method
Two steps to describe the substitution method is :
to guess the solution
to use mathematical induction to show that the guess is true or false.
Step by step
Solved in 2 steps
