Chapter 1: Introduction – 7.Main theorems about Subtract and Conquer Recurrence algorithms

Divide and Conquer algorithm in Vietnamese is Divide and conquer, then Subtract and Conquer algorithm is Subtract and Conquer algorithm is Subtract to conquer
I’m not sure if this translates properly, if there are mistakes, please comment, I will correct them

1.24 Master Theorem for Subtract and Conquer Recurrence

Because in the book the author wrote about this part quite briefly, I can refer to more information here

These theorems are used to determine Big-O complexity on recursive functions ~ that is, subproblems:

With the constants c, a > 0, b > 0, k ≥ 0 and the function f(n). If f(n) has complexity

O ( n k ) O ( n ^ { k } )$O(n^k)$ then

Theorem proof:
From the original formula we have:

1. T(n) = aT(nb) + f(n)
2. T(nb) = aT(n-2b) + f(nb)
3. T(n-2b) = aT(n-3b) + f(n-2b)

=>

BILLION ( n − b ) = a 2 BILLION ( n − 3 b ) + a f ( n − 2 b ) + f ( n − b ) T left ( n – b right ) = a ^ { 2 } T left ( n – 3 b right ) + af left ( n – 2 b right ) + f left ( n – b right )$T\left(n–b\right)=a^{2}T\left(n–3b\right)+af\left(n–2b\right)+f\left(n–b\right)$ (Substitute 3 for 2)
=>

$BILLION$ $($$n$ $)$$=$ $a$$3$$BILLION$ $($$n$$-$$3$$b$ $)$$+$ $a$$2$$f$ $($$n$$-$$2$$b$ $)$$+$$a$$f$ $($$n$$-$$b$ $)$$+$$f$ $($$n$ $)$ $T\; left\; (\; n\; right\; )\; =\; a\; ^\; \{\; 3\; \}\; T\; left\; (\; n\; –\; 3\; b\; right\; )\; +\; a\; ^\; \{\; 2\; \}\; f\; left\; (\; n\; –\; 2\; b\; right\; )\; +\; af\; left\; (\; n\; -b\; right\; )\; +\; f\; left\; (\; n\; right\; )$T ( n ) = a 3 T ( n – 3 b ) + a 2 f ( n – 2 b ) + a f ( n – b ) + f ( n ) (Substitute the above formula for 1)
=> T(n) =

i=0 big n/b Sigma ^ { i = 0 text { to n/b } }Σ i = 0 to n/b

aif (n−ib ) a ^ { i } f ( n – ib )a i f ( n − ib ) + constant, where

f (n−ib ) f ( n – ib )f ( n − ib ) has a complexity

O (n−ib ) O ( n – ib )O ( n − ib )
=>

BILLION (n )=O ( nk i=0 big /b ai ) T left ( n right ) = O left ( n ^ { k } Sigma ^ { i = 0 text { to n } / b } a ^ { i } right )T ( n ) = O ( n k Σ i = 0 to n / b a i )

=> From this formula, we have the same conclusion as picture 2
You can refer to the proof in the following link

1.25 Variant of Subtraction and Conquer Master Theorem

Solution to the equation

BILLION ( n ) = BILLION ( α n ) + BILLION ( ( first − α ) n ) + β n T ( n ) = T ( alpha ~ n ) + T ( ( 1 – alpha ) n ) + beta n$T(n)=T(\alpha n)+T((1-\alpha )n)+\beta n$ , where 0 < α < 1 and β > 0 are constants
is O(nlogn)

Example problem

A typical problem for this algorithm is finding the fibonacci number.
The rule of the Fibonacci sequence: the next number is equal to the sum of the previous 2 numbers, the first 2 numbers of the sequence are 0, 1. For example: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

Time complexity analysis
The above recursive function can be defined as T(n) = T(n-1) + T(n-2)
In case of Worst Case , let’s say T(n-1) T(n-2)
=> T(n) = 2T(n-1) + c
With f(n) = O(1) (constant c), k = 0, a = 2, b = 1
Applying the above theory, we have:

BILLION ( n ) = O ( n 0 2 n / first ) | T left ( n right ) = O left ( n ^ { 0 } 2 ^ { n / 1 } right )$T\left(n\right)=$O ( n 0 2 n /1 )

$=$ $O$ $($ $2$ $n$ $)$ $=\; O\; left\; (\; 2\; ^\; \{\; n\; \}\; right\; )$$=O\left(2^n\right)$

Concluding the theory of Subtract and Conquer, in the next article, I will present the method of guessing and confirming (Guessing and Confirming).
The article is a bit difficult about math, thank you everyone for reading this far