There may be times when you encounter a strange recurrence like this:

$$ T (n) = begin {cases}

c & n <7 \

2T left ( frac {n} {5} right) + 4T left ( frac {n} {7} right) + cn & n geq 7

end {cases} $$

If you are like me, you will realize that you can not use the Master Theorem and then you will think: "hmmm … maybe a recurrence tree analysis could work". Then you would realize that the tree begins to become very fast. After some searches on the Internet, you will see that the Akra-Bazzi method will work! Then you start to see it and you realize that you do not really want to do all the calculations. If you have been like me until now, you will love knowing that there is an easier way.

Leave $ c $ Y $ k $ Be positive constants.

So, let's go $ {a_1, a_2, ldots, a_k } $ be positive constants such that $ sum_1 ^ k a_i <1 $.

We must also have a recurrence of the form (like our previous example):

$$ begin {align}

T (n) & leq c & 0 <n < max {a_1 ^ {- 1}, a_2 ^ {- 1}, ldots, a_k ^ {- 1} } \

T (n) and leq cn + T (a_1 n) + T (a_2 n) + points T (a_k n) & n geq max {a_1 ^ {- 1}, a_2 ^ {- 1}, ldots, a_k ^ {- 1} }

end {align} $$

## Claim

Then I claim $ T (n) leq bn $ where $ b $ it is a constant (for example, asymptotically linear) and:

$$ b = frac {c} {1 – left ( sum_1 ^ k a_i right)} $$

## Induction test

**Base**: $ n < max {a_1 ^ {- 1}, a_2 ^ {- 1}, ldots, a_k ^ {- 1} } implies T (n) leq c <b <bn $

**Induction**: Suppose it is true for any $ n & # 39; <n $, so, we have

$$ begin {align}

T (n) & leq cn + T ( lfloor a_1 n rfloor) + T ( lfloor a_2 n rfloor) + dots + T ( lfloor a_k n rfloor) \

& leq cn + b lfloor a_1 n rfloor + b lfloor a_2 n rfloor + dots + b lfloor a_k n rfloor \

& leq cn + b a_1 n + b a_2 n + dots + b a_k n \

& = cn + bn sum_1 ^ k a_i \[0.5em]

& = frac {cn – cn sum_1 ^ k a_i} {1 – left ( sum_1 ^ k a_i right)} + frac {cn sum_1 ^ k a_i} {1 – left ( sum_1 ^ k a_i right)} \[0.5em]

& = frac {cn} {1 – left ( sum_1 ^ k a_i right)} \

& = bn & square

end {align} $$

Then we have $ T (n) leq bn implies T (n) = O (n) $.

## Example

$$ T (n) = begin {cases}

c & n <7 \

2T left ( frac {n} {5} right) + 4T left ( frac {n} {7} right) + cn & n geq 7

end {cases} $$

First we verify the coefficients within the sum of recursive calls to less than one:

$$ begin {align}

1 &> sum_1 ^ k a_i \

& = frac {1} {5} + frac {1} {5} + frac {1} {7} + frac {1} {7} + frac {1} {7} + frac { 1} {7} \[0.5em]

& = frac {2} {5} + frac {4} {7} \[0.5em]

& = frac {34} {35}

end {align} $$

Then we verify that the base case is less than the maximum of the inverses of the coefficients:

$$ begin {align}

n & < max {a_1 ^ {- 1}, a_2 ^ {- 1}, ldots, a_k ^ {- 1} } \

& = max {5, 5, 7, 7, 7, 7 } \

& = 7

end {align} $$

With these conditions fulfilled, we know $ T (n) leq bn $ where $ b $ is a constant equal to:

$$ begin {align}

b & = frac {c} {1 – left ( sum_1 ^ k a_i right)} \[0.5em]

& = frac {c} {1 – frac {34} {35}} \[0.5em]

& = 35c

end {align} $$

That's why we have:

$$ begin {align}

T (n) and ≤ 35cn \

land; T (n) and geq cn \

therefore, T (n) & = Theta (n)

end {align} $$

In the same way we can prove a limit for when. $ sum_1 ^ k = 1 $. The test will follow much of the same format:

Leave $ c $ Y $ k $ be positive constants such that $ k> 1 $.

So, let's go $ {a_1, a_2, ldots, a_k } $ be positive constants such that $ sum_1 ^ k a_i = 1 $.

We must also have a recurrence of the form (like our previous example):

$$ begin {align}

T (n) & leq c & 0 <n < max {a_1 ^ {- 1}, a_2 ^ {- 1}, ldots, a_k ^ {- 1} } \

T (n) and leq cn + T (a_1 n) + T (a_2 n) + points T (a_k n) & n geq max {a_1 ^ {- 1}, a_2 ^ {- 1}, ldots, a_k ^ {- 1} }

end {align} $$

## Claim

Then I claim $ T (n) leq n log_k n + beta n $ (We choose $ log $ base $ k $ why $ k $ will be the branch factor of the recursion tree) where $ alpha $ Y $ beta $ they are constants (for example, asymptotically linear) such that:

$$ beta = c $$

Y

$$ alpha = frac {c} { sum_1 ^ k a_i log_k a_i ^ {- 1}} $$

## Induction test

**Base**: $ n < max {a_1 ^ {- 1}, a_2 ^ {- 1}, ldots, a_k ^ {- 1} } implies T (n) leq c = beta < alpha n log_k n + beta n $

**Induction**: Suppose it is true for any $ n & # 39; <n $, so, we have

$$ begin {align}

T (n) & leq cn + T ( lfloor a_1 n rfloor) + T ( lfloor a_2 n rfloor) + dots + T ( lfloor a_k n rfloor) \

& leq cn + sum_1 ^ k ( alpha a_i n log_k a_i n + beta a_i n) \

& = cn + alpha n sum_1 ^ k (a_i log_k a_i n) + beta n sum_1 ^ k a_i \

& = cn + n sum_1 ^ k left (a_i log_k frac {n} {a_i ^ {- 1}} right) + beta n \

& = cn + alpha n sum_1 ^ k (a_i ( log_k n – log_k a_i ^ {- 1})) + beta n \

& = cn + alpha n sum_1 ^ k a_i log_k n – n sum_1 ^ k a_i log_k a_i ^ {- 1} + beta n \

& = n sum_1 ^ k a_i log_k n + beta n \

& = n log_k n + beta n & square

end {align} $$

Then we have $ T (n) leq n log_k n + beta n implies T (n) = O (n log n) $.

## Example

Let's modify that previous example that we use only a little:

$$ T (n) = begin {cases}

c & n <35 \

2T left ( frac {n} {5} right) + 4T left ( frac {n} {7} right) + T left ( frac {n} {35} right) + cn & n geq 35

end {cases} $$

First we verify the coefficients within the sum of recursive calls to one:

$$ begin {align}

1 & = sum_1 ^ k a_i \

& = frac {1} {5} + frac {1} {5} + frac {1} {7} + frac {1} {7} + frac {1} {7} + frac { 1} {7} + frac {1} {35} \[0.5em]

& = frac {2} {5} + frac {4} {7} + frac {1} {35} \[0.5em]

& = frac {35} {35}

end {align} $$

Then we verify that the base case is less than the maximum of the inverses of the coefficients:

$$ begin {align}

n & < max {a_1 ^ {- 1}, a_2 ^ {- 1}, ldots, a_k ^ {- 1} } \

& = max {5, 5, 7, 7, 7, 7, 35 } \

& = 35

end {align} $$

With these conditions fulfilled, we know $ T (n) leq n log n + beta n $ where $ beta = c $ Y $ alpha $ is a constant equal to:

$$ begin {align}

b & = frac {c} { sum_1 ^ k a_i log_k a_i ^ {- 1}} \[0.5em]

& = frac {c} { frac {2 log_7 5} {5} + frac {4 log_7 7} {7} + frac { log_7 35} {35}} \[0.5em]

& approx 1.048c

end {align} $$

That's why we have:

$$ begin {align}

T (n) & 1.048cn log_7 n + cn \

therefore, T (n) & = O (n log n)

end {align} $$