Introduction of Design and Analysis of Algorithm Study Notes with Example

                                                                     Design and Analysis of Algorithms

 Introduction to Analysis of Algorithms

An algorithm is a finite set of instructions that, if followed, accomplishes a particular task. Informally, an algorithm is any well defined computational procedure that takes some value or set of values as input and produces some value or set of values as output. Thus, an algorithm is a sequence of computational steps that transform the input into the output.

There are some terms related to the algorithms are given as follows

Computational Problem

A computational problem is a specification of the desired input-output relationship. It focuses on classifying computational problems according to their inherent difficulty and relating those classes to each other.

Instance

An instance of a problem is all the inputs needed to compute a solution to the problem. A computational problem can be viewed as an infinite collection of instances together with a solution for every instance.

Algorithm

An algorithm is a well defined computational procedure that transforms Inputs into outputs, achieving the desired input-output relationship^.

Correct Algorithm

A correct algorithm halts with the correct output for every input instance. We can say that the algorithm solves the problem.Correct Algorithm

Analysis of Algorithms

Analysis of algorithm depends upon various factors such as memory, communication bandwidth or computer hardware. The most often used for analyzing of algorithms is the computational time that an algorithm requires for completing the given task. By counting the number of steps, the runtime of an algorithm is measured.

Complexity

Algorithm can be classified by the amount of time they need to complete compared to their input size. The analysis of an algorithm focuses on the complexity of algorithm.

 

Time Complexity

The time complexity is a function that gives the amount of time required by  an algorithm to run to completion. The time complexity quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input..

Space Complexity

The space complexity is a function that gives the amount of space required by an algorithm to run to completion.

Key Points

• We usually refer the time complexity in three terms
• Best case time complexity
• Average case time complexity
• Worst case time complexity
• Worst case time complexity It is the function defined by the maximum amount of time needed by an algorithm for an input of size
• Average case time complexity It is the execution of an algorithm having

typical input data of size n.

• Best case time complexity It is the minimum amount of time that an algorithm requires for an input of size n.

 Asymptotic Analysis

This can be done by considering the following analysis

• It describes the behavior of function in the limit.
• There are multiple asymptotic notations those compare the sizes of

0 (Big Oh) .5_ {Asymptotic upper bound}

g2 (Big Omega)                                              {Asymptotic lower bound}
0 (Big Theta) — = {Asymptotic tight bound}

o (Small Oh) < {Tight upper bound}

co (Small Omega) —- > {Tight lower bound}

Asymptotic Notations-

The notations we use to describe the asymptotic running time of an algdrithm are defined in terms of functions whose domains are the set of natural numbers N = {0,1, 2…}

The asymptotic notations consist of the following useful notations

Big Oh (0)

If we write f(n) = 0(g (n)), then there exists a function f(n) such that

f(n) cg (n)

with any constant c.

Or we can say g(n) is an asymptotic upper bound for f(n).

e.g., 2n² = 0(n³) with constant c = 1.

Big Omega (Q)

If we write f (n) = E2 (g (n)), then there exists a function f (n) such that

f(n) cg (n)

with any constant c.

Function g(n) is an asymptotic lower bound for f(n).

e.g.,      1177 = E2 (log₂ n) with constant c = 1.

Big Theta ( )

If we write .f(n) =0 (g (n)), then there exists a function f (n) such that

c₁g (n) < f (n) c ₂g (n)

 with any positive constants c₁ and c₂.

Function g (n) is an asymptotically tight bound for f (n). ,

Theorem

f(n) = 9 (g (n)) if and only if f = 0 (g (n)) and f (n) = (g(n)),

Small Oh (o)

          Notation : If we write f (n) =ω (g (n)), then there exists a function such that

f(n) > c g(n),with any positive constant c.

Function g(n) is an asymptotically tight upper bound of f(n),

 Small Omega (0))

Notation If we write f (n) = w (g (n)), then there exists a function such that f(n) > cg (n),^– with any positive constant c.

g(n) is asymptotically tight lower bound of (n).

e.g,,                                                         n^2.00001 = w (n2)

and                                                   n²≠ω (n2)

Comparisons of a Symptomatic Notations Based on the Relational Properties

Assume, f(n) and g(n) are as asymptotically positive.

The relational properties are given as under

Transitivity

f (n) =  (g (n)) and g (n) =  (h (n))

f (n) =  (h(n))

This property is same for 0, Q, o and co .

Reflexivity

f (n) = 0 (f (n)) This property is same for 0 and Q.

Symmetry

 f (n) = 0 (g (n)) if and only if g (n) = 0 (f (n))

Transpose Symmetry

f (n) = 0 (g (n)) if and only if g (n) = Ω (f (n))

f (n) = 0 (g (n)) if and only if g (n) = w(f (n))

Recurrences

A recurrence is a function, defined in terms of

• One or more base cases  Itself with smaller arguments

                                                    T(n)= 1                            if n =1,

                                                                                             T(n — 1) + 1 if n > 1

                                                            T(n)= n

In algorithm analysis, we usually express both the recurrence and its solution using asymptotic notation.

Methods to Solve the Recurrence Relation There are two methods to solve the recurrence relation given as 1. Substitution method                                         2. Master method

Substitution Method

The substitution method is a condensed way of proving an asymptotic bound on a recurrence by induction. In the substitution method, instead of trying to find an exact closed form solution, we only try to find a closed form bound on the recurrence.

There are two steps in this method

• Guess the solution
• Use induction to find the constants and show that the solution works.

Key Points

 

• The substitution method is powerful approach that is able to prove upper bounds for almost all recurrences.
• The substitution method requires the use of induction.

Master Method

The master method gives us a quick way to find solutions to recurrence relations of the form T(n) = aT (n/ b) + f(n). where, a and b are constants, a ≥ 1 and b > 1 . Here, a represents how many recursive calls are made, b represents the factor by which the work is reduced in each recursive call. f(n) represents how much work is done by each call.

Solution of Recurrence Relation

•  The solution of the recurrence relation will be in the form of

f(n)

T(n)= n^logbba [U(n)]; h(n)⁼

n^{logh a}

■ Now, the values of U(n) and h(n) are related in three cases as follows

Case 1 If h(n) = nr, r < 0, then U (n) = 0 (1)

Case 2  If h(n) = nr, r > 0, then U (n) = 0 (d)

Case 3  If h(n) = (log₂ n)¹, i > 0, then U (n) =0(log 2 n)^{i +1}/  i+ 1

                                                                        T(n)= 0 (n log n)

---

Importance of Turing Machine Tutorial Notes Study Material with Examples

Follow Us on Social Platforms to get Updated : twiter,  facebook, Google Plus

Learn Turing Machine in Handbook Series:  Click here