1 Analysis of Framework
2 Measuring an input size
3 Units for measuring runtime
4 Worst case, Best case and Average case
5 Asymptotic Notations

**FUNDAMENTALS OF THE ANALYSIS OF
ALGORITHM EFFICIENCY**

*Fundamentals
of Analysis of Algorithm:*

*1
Analysis of Framework*

*2
Measuring an input size*

*3 Units
for measuring runtime*

*4 Worst
case, Best case and Average case*

*5
Asymptotic Notations*

**1 ANALYSIS FRAME WORK**

♦ there
are two kinds of efficiency

♦ **Time
efficiency** - indicates how fast an algorithm in question runs.

♦ **Space
efficiency** - deals with the extra space the algorithm requires.

**2 MEASURING AN INPUT SIZE**

♦
An algorithm's efficiency as a function of some
parameter n indicating the algorithm's input size.

♦
In most cases, selecting such a parameter is quite
straightforward.

♦
For example, it will be the size of the list for
problems of sorting, searching, finding the list's smallest element, and most
other problems dealing with lists.

♦
For the problem of evaluating a polynomial **p(x) = a** _{n}**x** ^{n}+ . . . + a** _{0}** of degree n, it will be
the polynomial's degree or the number of its coefficients, which is larger by
one than its degree.

♦
There are situations, of course, where the choice
of a parameter indicating an input size does matter.

♦ **Example **- computing the product of two
n-by-n matrices.

♦ There are
two natural measures of size for this problem.

♦
The matrix order n.

♦
The total number of elements N in the matrices being
multiplied.

♦
Since there is a simple formula relating these two
measures, we can easily switch from one to the other, but the answer about an
algorithm's efficiency will be qualitatively different depending on which of
the two measures we use.

♦
The choice of an appropriate size metric can be
influenced by operations of the algorithm in question. For example, how should
we measure an input's size for a spell-checking algorithm? If the algorithm
examines individual characters of its input, then we should measure the size by
the number of characters; if it works by processing words, we should count
their number in the input.

♦
We should make a special note about measuring size
of inputs for algorithms involving properties of numbers (e.g., checking
whether a given integer n is prime).

♦
For such algorithms, computer scientists prefer
measuring size by the number b of bits in the n's binary representation:

**b=|log _{2}n|+1**

♦
This metric usually gives a better idea about
efficiency of algorithms in question.

**3 UNITS FOR MEASURING RUN TIME:**

♦
We can simply use some standard unit of time
measurement-a second, a millisecond, and so on-to measure the running time of a
program implementing the algorithm.

♦
There are obvious drawbacks to such an approach.
They are

♦
Dependence on the speed of a particular computer

♦
Dependence on the quality of a program implementing
the algorithm

♦
The compiler used in generating the machine code

♦
The difficulty of clocking the actual running time
of the program.

♦
Since we are in need to measure algorithm
efficiency, we should have a metric that does not depend on these extraneous
factors.

♦
One possible approach is to count the number of
times each of the algorithm's operations is executed. This approach is both
difficult and unnecessary.

♦
The main objective is to identify the most
important operation of the algorithm, called

the basic
operation, the operation contributing the most to the total running time, and
compute the number of times the basic operation is executed.

**4 WORST CASE, BEST CASE AND
AVERAGE CASE EFFICIENCES**

♦
It is reasonable to measure an algorithm's
efficiency as a function of a parameter indicating the size of the algorithm's
input.

♦
But there are many algorithms for which running
time depends not only on an input size but also on the specifics of a
particular input.

♦
**Example,
sequential search**. This is a straightforward algorithm that searches
for a** **given item (some search key K)
in a list of n elements by checking successive elements of the list until
either a match with the search key is found or the list is exhausted.

♦
Here is the algorithm's pseudo code, in which, for
simplicity, a list is implemented as an array. (It also assumes that the second
condition A[i] i= K will not be checked if the first one, which checks that the
array's index does not exceed its upper bound, fails.)

**ALGORITHM **Sequential
Search(A[0..n -1], K)

//Searches for a given value in a given array by
sequential search //Input: An array A[0..n -1] and a search key K

//Output: Returns the index of the first element of
A that matches K // or -1 ifthere are no matching elements

i←0

**while **i < n
and A[i]** **≠** **K** do**

i←i+1

**if **i < n** return **i** else return **-1

♦
Clearly, the running time of this algorithm can be
quite different for the same list size n.

**Worst case efficiency**

♦
The worst-case efficiency of an algorithm is its
efficiency for the worst-case input of size n, which is an input (or inputs) of
size n for which the algorithm runs the longest among all possible inputs of
that size.

♦
In the worst case, when there are no matching
elements or the first matching element happens to be the last one on the list,
the algorithm makes the largest number of key comparisons among all possible
inputs of size n:

**C _{worst} (n) = n.**

♦
The way to determine is quite straightforward

♦
To analyze the algorithm to see what kind of inputs
yield the largest value of the basic operation's count C(n) among all possible
inputs of size n and then compute this worst-case value **C** _{worst}**(n)**

♦
The worst-case analysis provides very important
information about an algorithm's efficiency by bounding its running time from
above. In other words, it guarantees that for any instance of size n, the
running time will not exceed **C** _{worst}**(n)** its running time on the worst-case inputs.

**Best case Efficiency**

♦
The best-case efficiency of an algorithm is its
efficiency for the best-case input of size n, which is an input (or inputs) of
size n for which the algorithm runs the fastest among all possible inputs of
that size.

♦
We can analyze the best case efficiency as follows.

♦
First, determine the kind of inputs for which the
count C (n) will be the smallest among all possible inputs of size n. (Note
that the best case does not mean the smallest input; it means the input of size
n for which the algorithm runs the fastest.)

♦
Then ascertain the value of C (n) on these most
convenient inputs.

♦
Example- for sequential search, best-case inputs
will be lists of size n with their first elements equal to a search key;
accordingly, C_{best}(n) = 1.

♦
The analysis of the best-case efficiency is not
nearly as important as that of the worst-case efficiency.

♦
But it is not completely useless. For example,
there is a sorting algorithm (insertion sort) for which the best-case inputs
are already sorted arrays on which the algorithm works very fast.

♦
Thus, such an algorithm might well be the method of
choice for applications dealing with almost sorted arrays. And, of course, if
the best-case efficiency of an algorithm is unsatisfactory, we can immediately
discard it without further analysis.

**Average case efficiency**

♦
It yields the information about an algorithm about
an algorithm‘s behaviour on a ―typical‖ and ―random‖ input.

♦
To analyze the algorithm's average-case efficiency,
we must make some assumptions about possible i*n*puts of size n.

♦
The investigation of the average case efficiency is
considerably more difficult than investigation of the worst case and best case
efficiency.

♦
It involves dividing all instances of size n .into
several classes so that for each instance of the class the number of times the
algorithm's basic operation is executed is the same.

♦
Then a probability distribution of inputs needs to
be obtained or assumed so that the expected value of the basic operation's
count can then be derived.

The
average number of key comparisions C_{avg}(n) can be computed as
follows,

♦
let us consider again sequential search. The
standard assumptions are,

♦
In the case of a successful search, the probability
of the first match occurring in the ith position of the list is pin for every
i, and the number of comparisons made by the algorithm in such a situation is
obviously i.

♦
In the case of an unsuccessful search, the number
of comparisons is n with the probability of such a search being (1 - p).
Therefore,

♦
Example, if p = 1 (i.e., the search must be
successful), the average number of key comparisons made by sequential search is
(n + 1) /2.

♦
If p = 0 (i.e., the search must be unsuccessful),
the average number of key comparisons will be n because the algorithm will
inspect all n elements on all such inputs.

**5 Asymptotic Notations**

Step
count is to compare time complexity of two programs that compute same function
and also to predict the growth in run time as instance characteristics changes.
Determining exact step count is difficult and not necessary also. Because the
values are not exact quantities. We need only comparative statements like c_{1}n^{2}
≤ t_{p}(n) ≤ c_{2}n^{2}.

For
example, consider two programs with complexities c_{1}n^{2} + c_{2}n
and c_{3}n respectively. For small values of n, complexity depend upon
values of c_{1}, c_{2} and c_{3}. But there will also
be an n beyond which complexity of c_{3}n is better than that of c_{1}n^{2}
+ c_{2}n.This value of n is called break-even point. If this point is
zero, c _{3}n is always faster (or at least as fast). Common asymptotic
functions are given below.

**Big‘Oh’Notation(O)**

O(g(n)) =
{ f(n) : there exist positive constants c and n_{0} such that 0 ≤ f(n)
≤ cg(n) for all n ≥

n_{0}
}

It is the
upper bound of any function. Hence it denotes the worse case complexity of any
algorithm. We can represent it graphically as

Find the
Big ‗Oh‘ for the following functions:

__Linear Functions__

**Example 1.6 **f(n) = 3n
+ 2

General
form is f(n) ≤ cg(n)

When n ≥ 2, 3n
+ 2 ≤ 3n + n = 4n

Hence
f(n) = O(n), here c = 4 and n_{0} = 2

When n ≥ 1, 3n
+ 2 ≤ 3n + 2n = 5n

Hence
f(n) = O(n), here c = 5 and n_{0} = 1

Hence we
can have different c,n_{0} pairs satisfying for a given function.

**Example **f(n) = 3n
+ 3

When n ≥
3, 3n + 3 ≤ 3n + n = 4n Hence f(n) = O(n), here c = 4 and n_{0} = 3

**Example**

f(n) =
100n + 6

When n ≥
6, 100n + 6 ≤ 100n + n = 101n Hence f(n) = O(n), here c = 101 and n_{0}
= 6

__Quadratic Functions__

**Example 1.9**

f(n) =
10n^{2} + 4n + 2

When n ≥ 2, 10n^{2}
+ 4n + 2 ≤ 10n^{2} + 5n

When n ≥
5, 5n ≤ n^{2}, 10n^{2} + 4n + 2 ≤ 10n^{2} + n^{2}
= 11n^{2} Hence f(n) = O(n^{2}), here c = 11 and n_{0}
= 5

**Example 1.10**

f(n) =
1000n^{2} + 100n - 6

f(n) ≤
1000n^{2} + 100n for all values of n.

When n ≥
100, 5n ≤ n^{2}, f(n) ≤ 1000n^{2} + n^{2} = 1001n^{2}
Hence f(n) = O(n^{2}), here c = 1001 and n_{0} = 100

__Exponential Functions__

**Example 1.11 **f(n) =
6*2^{n} + n^{2}

When n ≥ 4, n^{2}
≤ 2^{n}

So f(n) ≤
6*2^{n} + 2^{n} = 7*2^{n}

Hence
f(n) = O(2^{n}), here c = 7 and n_{0} = 4

__Constant Functions__

**Example 1.12 **f(n) = 10

f(n) =
O(1), because f(n) ≤ 10*1

**OmegaNotation(Ω)**

Ω (g(n))
= { f(n) : there exist positive constants c and n_{0} such that 0 ≤
cg(n) ≤ f(n) for all n

≥ n_{0}
}

It is the
lower bound of any function. Hence it denotes the best case complexity of any
algorithm. We can represent it graphically as

**Example 1.13 **f(n) = 3n
+ 2

3n + 2
> 3n for all n. Hence f(n) = Ω(n)

Similarly
we can solve all the examples specified under Big ‗Oh‘.

_{The}**taNotation(Θ)**

Θ(g(n)) =
{f(n) : there exist positive constants c_{1},c_{2} and n_{0}
such that c_{1}g(n) ≤f(n) ≤c_{2}g(n) for all n ≥ n_{0}
}

If f(n) =
Θ(g(n)), all values of n right to n_{0} f(n) lies on or above c_{1}g(n)
and on or below c_{2}g(n). Hence it is asymptotic tight bound for f(n).

__Little-O Notation__

For
non-negative functions, f(n) and g(n), f(n) is little o of g(n) if and only if
f(n) = O(g(n)), but f(n) ≠ Θ(g(n)). This is denoted as "f(n) =
o(g(n))".

This
represents a loose bounding version of Big O. g(n) bounds from the top, but it
does not bound the bottom.

**Little Omega Notation**

For
non-negative functions, f(n) and g(n), f(n) is little omega of g(n) if and only
if f(n) = Ω(g(n)), but f(n) ≠ Θ(g(n)). This is denoted as "f(n) =
ω(g(n))".

Much like
Little Oh, this is the equivalent for Big Omega. g(n) is a loose lower boundary
of the function f(n); it bounds from the bottom, but not from the top.

**Conditional asymptotic notation**

Many algorithms are easier to analyse if initially
we restrict our attention to instances whose size satisfies a certain
condition, such as being a power of 2. Consider, for example, the divide and
conquer algorithm for multiplying large integers that we saw in the
Introduction. Let *n* be the size of
the integers to be multiplied.

The algorithm proceeds directly if *n = 1*, which requires *a* microseconds for an appropriate
constant *a*. If *n>1*, the algorithm proceeds by multiplying four pairs of
integers of size three if we use the better algorithm).
Moreover, it takes a linear amount of time to carry out additional tasks. For
simplicity, let us say that the additional work takes at most *bn* microseconds for an appropriate
constant *b*.

**Properties of Big-Oh Notation**

Generally,
we use asymptotic notation as a convenient way to examine what can happen in a
function in the worst case or in the best case. For example, if you want to
write a function that searches through an array of numbers and returns the
smallest one:

*function
find-min(array a[1..n]) let j :=*

*for i := 1 to n:*

*j :=
min(j, a[i] ) repeat*

*return j end*

Regardless
of how big or small the array is, every time we run find-min, we have to
initialize the i and j integer variables and return j at the end. Therefore, we
can just think of those parts of the function as constant and ignore them.

So, how
can we use asymptotic notation to discuss the find-min function? If we search
through an array with 87 elements, then the for loop iterates 87 times, even if
the very first element we hit turns out to be the minimum. Likewise, for n elements,
the for loop iterates n times. Therefore we say the function runs in time O(n).

*function find-min-plus-max(array
a[1..n] )*

// *First, find the smallest element in the array let j
:= ;*

*for i := 1 to n:*

*j :=
min(j, a[i] ) repeat*

*let minim := j*

// *Now, find the biggest element, add it to the
smallest and j := ;*

*for i := 1 to n:*

*j :=
max(j, a[i] ) repeat*

*let maxim := j*

*// return the sum of the two
return minim + maxim;*

*end*

What's the running time for find-min-plus-max?
There are two for loops, that each iterate n times, so the running time is
clearly O(2n). Because 2 is a constant, we throw it away and write the running
time as O(n). Why can you do this? If you recall the definition of Big-O
notation, the function whose bound you're testing can be multiplied by some
constant. If f(x)=2x, we can see that if g(x) = x, then the Big-O condition
holds. Thus O(2n) = O(n). This rule is general for the various asymptotic
notations.

**Recurrence**

When an
algorithm contains a recursive call to itself, its running time can often be
described by a recurrence

**Recurrence Equation**

A
recurrence relation is an equation that recursively defines a sequence. Each
term of the sequence is defined as a function of the preceding terms. A
difference equation is a specific type of recurrence relation.

An
example of a recurrence relation is the logistic map:

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Analysis and Design of Algorithm : Fundamentals of the Analysis of Algorithm Efficiency |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.