1 month, 1 week

Analysis of Algorithm

When analyzing algorithms, recall that we only care about asymptotic behavior. Recursive algorithms are no different. Rather than solve exactly the recurrence relation associated with the cost of an algorithm, it is enough to give an asymptotic characterization. The Master's method is the most useful and easy method to compute the time complexity function of recurrence relations. The approach was first presented by Jon Bentley, Dorothea Haken, and James B. Saxe in 1980, where it was described as a "unifying method" for solving such recurrences. The name "master theorem" was popularized by the widely used algorithms textbook Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein.

Algorithms are usually grouped into different types, some examples include greedy algorithms, recursive algorithms, dynamic programming, divide and conquer, etc. The master theorem is a method used to provide asymptotic analysis of recurrence relations that occur in many divide and conquer algorithms. A divide and conquer algorithm is an algorithm that solves a problem by breaking it up into smaller sub-problems first, then solves each subproblem individually before combining the results into the solution for the main larger problem.

There are three methods used to analyze recurrence relations:

Substitution Method: Using mathematical induction to prove an assumed solution.
Recurrence Tree Method: Adding the time taken by every level in a recurrence tree.
Master Method: Direct method to find the solution using formulas.

A recurrence relation is an equation that defines a sequence based on a rule that gives the next term as a function of the previous term(s) It’s a lot like recursive code:

- At least one base case and at least one recursive case

- Each case should include the values for n to which it corresponds

- The recursive case should reduce the input size in a way that eventually triggers the base case

- The cases of your recurrence usually correspond exactly to the cases of the code

• The time complexity of the algorithm is represented in the form of recurrence relation.
• When analyzing algorithms, recall that we only care about asymptotic behavior.
• Rather than solving exactly the recurrence relation associated with the cost of an algorithm, it is sufficient to give an asymptotic characterization.

Oh, and Omega, and Theta

• Big oh notation ( O ) is used to describe asymptotic upper bound.

- My code takes at most this long to run

• Big-Omega (Ω) is an asymptotic lower bound.

- My code takes at least this long to run

• Big Theta (Θ) is “equal to”

- My code takes “exactly”* this long to run

- *Except for constant factors and lower order terms

- Only exists when Big-Oh == Big-Omega!

• In industry, people often use Big-Oh to mean “Tight Big-Oh” and use it even when a Big-Theta exists.

Name	Big O
Constant	O(c)
Linear	O(n)
Quadratic	O(n²)
Cubic	O(n³)
Exponential	O(2ⁿ)
Logarithmic	O(log(n))
Log Linear	O(nlog(n))

Master's Method for Dividing Functions

The master theorem always yields asymptotically tight bounds to recurrences from divide and conquer algorithms that partition an input into smaller subproblems of equal sizes, solve the subproblems recursively, and then combine the subproblem solutions to give a solution to the original problem. The time for such an algorithm can be expressed by adding the work that they perform at the top level of their recursion (to divide the problems into subproblems and then combine the subproblem solutions) together with the time made in the recursive calls of the algorithm. If T(n) denotes the total time for the algorithm on an input of size n, and f(n) denotes the amount of time taken at the top level of the recurrence then the time can be expressed by a recurrence relation that takes the form:

Used to directly calculate the time complexity function of 'dividing' recurrence relations of the form:
• T(n) = aT(n/b) + f(n)
• where f(n) = θ(n^klog^pn)

• Compare log_ba and k to decide the final time complexity function.

a represents the number of subproblems in the recursion, and it must be greater or equal to one (a >= 1).

n/b is assumed to have the same size for each subproblem, and b must be greater than one (b > 1) to ensure a proper divide and conquer recurrence analysis.

Master's Theorem states that:

Case 1) If log_ba > k then:
- T(n) = θ(n^log_ba)
Case 2) If log_ba = k, then:
- a) If p > -1, then T(n) = θ(n^klog^(p+1)n)
- b) If p = -1, then T(n) = θ(n^k loglogn)
- c) p < -1, then T(n) = θ(n^k) ,
Case 3) If log_ba < k, then:
- If p >= 0, then T(n) = θ(n^klog^pn)
- If p < 0, then T(n) = θ(n^k)

To calculate log_ba and compare it with f(n) to decide the final time complexity of the recurrence relation T(n).

The idea behind Master's algorithm is based on the computation of n^log_ba and comparing it with f(n). The time complexity function comes out to be the one overriding the other.

Master's Theorem for Decreasing Functions

Used to directly calculate the time complexity function of 'decreasing' recurrence relations of the form:
- T(n) = aT(n - b) + f(n)
f(n) = (n^k)
The value of 'a' will decide the time complexity function for the 'decreasing' recurrence relation.

where:
n = input size (or the size of the problem)
a = count of subproblems in the decreasing recursive function
n - b = size of each subproblem (Assuming size of each subproblem is same)

f(n) is asymptotically positive. (Asymptotically positive means that the function is positive for all sufficiently large n.)

The theorem is as follows: If T(n) = a T(n-b) + f(n),

where a ≥ 1, b > 0, & f(n) = O(n^k ), and k ≥ 0

Case 1: if a = 1,

T(n) = O (n * f(n)) or O (n^k+1)

1) T(n) = T(n – 1 ) + 1 O(n)

2) T(n) = T(n – 1 ) + n O(n² )

3) T(n) = T(n – 1 ) + log n O(n log n )

Case 2: if a > 1,

T(n) = O (a^n/b * f(n)) or O (a^n/b * n^k )

1) T(n) = 2T(n – 1 ) + 1 O(2ⁿ )

2) T(n) = 3T(n – 1 ) + 1 O(3ⁿ )

3) T(n) = 2T(n – 1 ) + n O(n 2ⁿ )

Case 3: if a < 1,

T(n) = O (f(n)) or O (n^k )

Limitations

We cannot apply the master’s theorem in the following cases:

T(n) is not monotone. eg. T(n) = sin(n)
f(n) is not a polynomial. eg. f(n) = 2ⁿ
a is not a constant. eg. a = 2n

Merge Sort: T(n) = 2T(n/2) + Θ(n). It falls in case 2 as c is 1 and Log_ba is also 1.

So the solution is Θ(n Logn) .

Binary Search: T(n) = T(n/2) + Θ(1). It also falls in case 2 as c is 0 and Log_ba is also 0.

So the solution is Θ(Logn) .

Akra–Bazzi Theorem

The Akra–Bazzi method, or Akra–Bazzi theorem, is used to analyze the asymptotic behavior of the mathematical recurrences that appear in the analysis of divide and conquer algorithms where the sub-problems have substantially different sizes. It is a generalization of the master theorem for divide-and-conquer recurrences, which assumes that the sub-problems have equal size.

The recurrence relation form limits the usability of the Master’s theorem. Following are three recurrences that cannot be solved directly using the master’s theorem:

$\large{T(n) = 3T(\frac{n}{5}) + 2T(\frac{n}{5}) + \theta(n)}$

$\large{T(n) = \frac{1}{3}T(\frac{n}{3}) + \theta(\frac{1}{n})}$

$\large{T(n) = 9T(\frac{n}{3}+\log n) + \theta(n)}$

The Akra-Bazzi method can be applied to the recurrences of the following form:

$T(n)=\sum_{i=1}^{k} a_{i} T(b_{i}n+h_{i}(n))+g(n)$

where, $a_{i}$ and $b_{i}$ are constants such that:

$\ a_{i}>0$

$\ 0<b_{i}<1 \textnormal{ i.e. in the range (0, 1)}$

$\ g(n)\ \epsilon\ O(n^{c}) \textnormal{ i.e. }g(n) \textnormal{ must have a polynomial upperbound}$

$\ h_{i}(x)\ \epsilon\ O(\large\frac{n}{(logn)^{2}}\normalsize)$

Next, find p such that

$\large{\sum_{i=1}^k a_ib_i^p=1}$

Then

$\large{T(n)\epsilon\ \theta(n^{p}(1+\int_{1}^{n}\frac{g(u)}{u^{p+1}}du))}$

Example 1.

$\large{T(n) = 3T(\frac{n}{5}) + 2T(\frac{n}{5}) + \theta(n)}$

a₁= 3

b₁= $\large \frac{1}{5}$

a₂= 2

b₂= $\large \frac{1}{5}$

b₁ and b₂ are in the range (0, 1)

g(n) = θ(n) which is O(n^c), here c can be 1.

In this problem h₁(n) and h₂(n) are not present.
Here p=1 satisfies

$3*\large {\frac{1}{5}^p}\normalsize +2*\large {\frac{1}{5}^p}\normalsize=1.$

Finally,

$n^{1}(1+\int_{1}^{n}\large\frac{u}{u^{1+1}}\normalsize du)$

   $n(1+\log{n}-\log{1})$

$n+n\log{n}$

$\theta(n\log{n})$

Example 2.

$\large{T(n) = \frac{1}{3}T(\frac{n}{3}) + \theta(\frac{1}{n^{2}})}$

a = $\large \frac{1}{3}$

b = $\large \frac{1}{3}$

g(n) = $\theta(n^2)$

b is in the range (0, 1)

g(n) = θ(n^2) which is in O(n^c), here c can be 1.

In this problem h(n) is not present.
Here p= – 1 satisfies

$\large\frac{1}{2}\normalsize*\large\frac{1}{2}^p\normalsize=1$

Finally,

$n^{-1}(1+\int_{1}^{n}\large\frac{\frac{1}{u}}{u^{-1+1}}\normalsize du)$

$\large\frac{1}{n}\normalsize(1+\int_{1}^{n}\large\frac{1}{u}\normalsize du)$

$\large\frac{1}{n}\normalsize(1+[\log u]_{1}^{n})$

$\large\frac{1}{n}\normalsize(1+\log n)$

$\theta(\large\frac{\log n}{n}\normalsize)$

Example 3.

$\large{T(n) = 9T(\frac{n}{3}+\log n) + \theta(n)}$

a = 9

b = $\large\frac{1}{3}$

g(n) = θ(n) $\theta(n)$

b is in the range(0, 1)

g(n) = $\theta(n)$ which is O(n^c), here c can be 1.

h(n) = $\log{n}$ which is $O(\large\frac{n}{(logn)^{2}}\normalsize)$

Here p=2 satisfies

$9*\large\frac{1}{3}^p\normalsize=1$

Finally,

$n^{2}(1+\int_{1}^{n}\large\frac{u}{u^{2+1}}\normalsize du)$

$n^{2}(1+\int_{1}^{n}\large\frac{1}{u^{2}}\normalsize du)$

$n^{2}(1+[-\large\frac{1}{u}\normalsize]_{1}^{n})$

$n^{2}(2-\large\frac{1}{n}\normalsize)$

$2n^{2}-n$

$\theta(n^{2})$

Advantages:

Works for many divides and conquer algorithms.
Has a lesser constraint over the format of the recurrence than Master’s Theorem.
p can be calculated using numerical methods for complex recurrence relations.

Disadvantages: