Algorithm Analysis Techniques

Algorithm analysis techniques:

Analysis of algorithms is the process of analysing the problem solving capability of the algorithm in terms of the time and size of the memory for storage during implementation is required. However, the main concern of analysis of algorithm is the required time or performance.

Generally, we perform the following types of analysis:

      I.            Worst Case:

The worst case running time complexity of an algorithm gives us an upper bound on the running time of any input instance.

   II.            Best Case:

Best case represents the minimum number of steps taken by the algorithm or any input instance i.e. it gives us a lower bound on the running time for any input.

III.            Average Case:

It represents an average number of steps taken by the algorithm on any input instance.

IV.            Amortized:

A sequence of operations applied to any input instance averaged over time.

Various basic algorithm analysis techniques are discussed below:

•   Asymptotic Notation:

The Asymptotic behaviour of a function f(n) refers to the growth of f(n) as n gets larger. We typically ignore the small values of n since we’re usually interested in estimating how slow the program will be on large inputs.

Ø The Θ Notation:

The Θ Notation bounds a function from above and below, so it defines exact asymptotic behaviour of the function f(n)=Θg(n) if and only if there exists positive constants c₁, c₂, n₀ such that c₁g(n)≤f(n)≤c₂g(n) for all n≥n₀.

Ø The O Notation:

The O Notation bounds a function only from above, hence if defines an upper bound of an algorithm. The function is f(n)=Og(n) ) if and only if there exists positive constants c, n₀ such that f(n)≤cg(n) for all n≥n₀.

Ø The Ω Notation:

Ω provides an asymptotic lower bound of a function. This notation can be useful when we want to compute the lower bound on the time complexity of an algorithm. The function is f(n)=Ωg(n) if and only if there exists positive constants c, n₀ such that cg(n)≤ f(n) for all n≥n₀.

•  Solving Recurrence equations:

A recurrence is an equation or in-equality that describes a function in terms of its value on smaller inputs.

e.g.: If the problem size is small enough, like n<c, where c is a constant, then the solution takes constant time which is written as Θ(1). If the division of the problem yields a number of sub problems of size n/b, then to solve the problem, the required time is .If we consider the time required for combining the results of sub problem is C(n), then the recurrence relation can be written as:

A recurrence relation can be solved using the following methods:

I.                  Substitution Method:

In this method, we guess a bound and using mathematical induction, we prove that our assumption was correct.

II.               Recursion Tree Method:

This method covert the recurrence into a tree whose nodes represents the costs incurred at various levels of the recursion. We use techniques for bounding summations to solve the recurrence.

III.           Master Method:

The Master method provides bounds for the recurrence of the form:

, where a≥1, b>1 and f(n) is a given function.  

•  Amortized Analysis:

Amortized analysis is generally used for certain algorithms where a sequence of similar operations is performed. Characteristics of the analysis is described below:

§  Amortized analysis provides a bound on the actual cost of the entire sequence instead of bounding the cost of sequence of separately.

§  Amortized analysis differs from average case analysis; probability isn’t involved in amortized analysis. Amortized analysis guarantees the average performance of each operation in the worst case.

• Aggregate method:

The aggregate method gives a global view of a problem. In this method, if n operations take worst case time T(n) in total, then the amortized cost of each operation is T(n)/n. Though different operations may take different time, in this method, varying cost is neglected.

•    Accounting Method:

In this method, different charges are assigned to different operations according to their actual cost. If the amortized cost of an operation exceeds its actual cost, the difference is assigned to the object as credit. This credit helps to pay for later operations for which the amortized cost is less than the actual cost.

•    Potential Method:

This method represents the prepaid work as potential energy instead of considering prepaid work as credit. The energy can be released to pay for future operations.