Master Theorem algorithm (Master Theorem)

What is the mechanics theorem (Master Theorem)?

We use the Theorem theorem (Master Theorem) to effectively solve the following recursive formulas:

T (n) = aT (n / b) + cn ^ k where a> = 1, b> 1

The original problem is divided into a subproblem with size each of n / b, the cost of synthesizing subproblems is f (n).

Example: Alignment algorithm divided into 2 subproblems, size n / 2. The cost of synthesizing 2 subproblems is O (n).

Worker theorem

a> = 1, b> 1, c, k are constants. T (n) recursively defines non-negative parameters

T (n) = aT (n / b) + cn ^ k + If a> b ^ k then T (n) = O (n ^ (logab)) + If a = b ^ k then T (n) = O (n ^ k.lgn) + If a

Note: Not every case applies the mechanic theorem

Eg: T (n) = 2T (n / 2) + nlogn a = 2, b = 2, but the integer k is not defined

According to Tutorialspoint

Previous lesson: Dynamic programming (Dynamic Programming)

Next lesson: Linked list data structure (Linked List)