Master theorm 1

#1

what is the use of master theorm 1

#2

You must have written many programs using recursion. But, have you ever wondered, How to compute there time complexities?

Here’s your answer:

The Master Theorem is one of the way to compute or analyze the time complexity of divide and conquer algorithms (i.e. using recurrence).

It gives a short-hand simple formula for solving recurrences of the form
T(n)= A T(n/b) + n^k, up to order.

Explanation:
This is the recurrence you get from an algorithm that makes A recursive calls, each of size n/b, and in addition takes time n^k (to divide the problem into recursive calls, or to conquer, by combining the answers to recursive calls.)

There are more general versions of the Master Theorem than what I stated above, but the main use is for the above form.

Hope, this would help.
Give a like, if you are satisfied.

1 Like
#3

Mark it as resolved, please.

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

1 Like