IMPOTANCE OF ALGORITHM ANALYSIS

In the analysis of the algorithm, it generally focused on CPU (time) usage, Memory usage,
Disk usage, and Network usage. All are important, but the most concern is about the CPU
time.
Performance: How much time/memory/disk/etc. is used when a program is run. This
depends on the machine, compiler, etc. as well as the code we write.
Complexity: How do the resource requirements of a program or algorithm scale, i.e. what
happens as the size of the problem being solved by the code gets larger.
Algorithm Analysis:
Algorithm analysis is an important part of computational complexity theory, which provides
theoretical estimation for the required resources of an algorithm to solve a specific
computational problem. Analysis of algorithms is the determination of the amount of time
and space resources required to execute it.
Why Analysis of Algorithms is important?

• To predict the behavior of an algorithm without implementing it on a specific

computer.
• It is much more convenient to have simple measures for the efficiency of an
algorithm than to implement the algorithm and test the efficiency every time a
certain parameter in the underlying computer system changes.
• It is impossible to predict the exact behavior of an algorithm. There are too many
influencing factors.
• The analysis is thus only an approximation; it is not perfect.
• More importantly, by analyzing different algorithms, we can compare them to
determine the best one for our purpose.

Time complexity
he time complexity of an algorithm quantifies the amount of time taken by an algorithm
to run as a function of the length of the input. Note that the time to run is a function of
the length of the input and not the actual execution time of the machine on which the
algorithm is running on.

Space Complexity:
The space complexity of an algorithm quantifies the amount of space taken by an
algorithm to run as a function of the length of the input.
In the worst-case analysis, we calculate the upper bound on the running time of an
algorithm. We must know the case that causes a maximum number of operations to be
executed. For Linear Search, the worst case happens when the element to be searched (x in
the above code) is not present in the array. When x is not present, the search() function
compares it with all the elements of arr[] one by one. Therefore, the worst-case time
complexity of linear search would be Θ(n). Average Case Analysis (Sometimes done)

In average case analysis, we take all possible inputs and calculate computing time for all
of the inputs. Sum all the calculated values and divide the sum by the total number of
inputs. We must know (or predict) the distribution of cases. For the linear search problem,
let us assume that all cases are uniformly distributed (including the case of x not being
present in the array). So we sum all the cases and divide the sum by (n+1). Following is the
value of average-case time complexity.

In the best case analysis, we calculate the lower bound on the running time of an
algorithm. We must know the case that causes a minimum number of operations to be
executed. In the linear search problem, the best case occurs when x is present at the first
location. The number of operations in the best case is constant (not dependent on n). So
time complexity in the best case would be Θ(1)

Asymptotic Analysis
is the big idea that handles issues in analyzing algorithms. In Asymptotic Analysis, we
evaluate the performance of an algorithm in terms of input size (we don’t measure the
actual running time). We calculate, how the time (or space) taken by an algorithm
increases with the input size.

Asymptotic Notations
Asymptotic notations are mathematical tools to represent the time complexity of
algorithms for asymptotic analysis
Time function of an algorithm is represented by T(n) where n-- is input size
We have some asymptotic notations
Ω Notation (BIG OMEGA )
O (big oh)
Θ(BIG theta)
Big oh – O
The Big O notation defines an upper bound of an algorithm, it
bounds a function only from above
O(g(n)) = { f(n): there exist positive constants c and
n0 such that 0 <= f(n) <= c*g(n) for
all n >= n0}

Ω big omega
Just as Big O notation provides an asymptotic upper bound on a
function, Ω notation provides an asymptotic lower bound.
Ω Notation can be useful when we have a lower bound on the time
complexity of an algorithm. As discussed in the previous post, the best
case performance of an algorithm is generally not useful, the Omega
notation is the least used notation among all three.
For a given function g(n), we denote by Ω(g(n)) the set of functions
Ω (g(n)) = {f(n): there exist positive constants c and
n0 such that 0 <= c*g(n) <= f(n) for
all n >= n0}.

Θ(BIG theta)
The theta notation bounds a function from above and below, so it defines
exact asymptotic behaviour. A simple way to get the Theta notation of
an expression is to drop low-order terms and ignore leading constants.

Little ο
Big-Ο is used as a tight upper-bound on the growth of an algorithm’s effort (this effort is
described by the function f(n)), even though, as written, it can also be a loose upper-bound.
“Little-ο” (ο()) notation is used to describe an upper-bound that cannot be tight.
Definition : Let f(n) and g(n) be functions that map positive integers to positive real
numbers. We say that f(n) is ο(g(n)) (or f(n) Ε ο(g(n))) if for any real constant c > 0, there
exists an integer constant n0 ≥ 1 such that 0 ≤ f(n) < c*g(n).

Little ω
Definition : Let f(n) and g(n) be functions that map positive integers
to positive real numbers. We say that f(n) is ω(g(n)) (or f(n) ∈ ω(g(n)))
if for any real constant c > 0, there exists an integer constant n0 ≥ 1
such that f(n) > c * g(n) ≥ 0 for every integer n ≥ n0.
Recurrence Relation
A recurrence is an equation or inequality that describes a function in terms of its values on
smaller inputs. To solve a Recurrence Relation means to obtain a function defined on the
natural numbers that satisfy the recurrence.
For Example, the Worst Case Running Time T(n) of the MERGE SORT Procedures is described
by the recurrence.
T (n) = θ (1) if n=1
2TDAA Recurrence Relation + θ (n) if n>1
There are four methods for solving Recurrence:
1.Substitution Method
2.Iteration Method
3.Recursion Tree Method
4.Master Method

1. Substitution Method:
The Substitution Method Consists of two main steps:
1. Guess the Solution.
2. Use the mathematical induction to find the boundary condition and shows that
the guess is correct.

For Example1 :: Solve the equation by Substitution Method.

T (n) = T +n
We have to show that it is asymptotically bound by O (log n).
Solution:
For T (n) = O (log n)
We have to show that for some constant c
T (n) ≤c logn.
Put this in given Recurrence Equation.

T (n) ≤c logDAA Recurrence Relation+ 1

≤c logDAA Recurrence Relation+ 1 = c logn-clog2 2+1
≤c logn for c≥1
Thus T (n) =O logn.

2.Iteration Methods
It means to expand the recurrence and express it as a summation of terms of n and
initial condition.
Example1: Consider the Recurrence

T (n) = 1 if n=1
= 2T (n-1) if n>1

Solution:

T (n) = 2T (n-1)
= 2[2T (n-2)] = 2 2T (n-2)
= 4[2T (n-3)] = 2 3T (n-3)
= 8[2T (n-4)] = 2 4T (n-4) (Eq.1)

Repeat the procedure for i times

T (n) = 2 i T (n-i)
Put n-i=1 or i= n-1 in (Eq.1)
T (n) = 2 n-1 T (1)
= 2 n-1 .1 {T (1) =1 .....given}
= 2 n-1
3. Recursion Tree Method

1. Recursion Tree Method is a pictorial representation of an iteration method which is in

the form of a tree where at each level nodes are expanded.

2. In general, we consider the second term in recurrence as root.

3. It is useful when the divide & Conquer algorithm is used.

4. It is sometimes difficult to come up with a good guess. In Recursion tree, each root and
child represents the cost of a single subproblem.

5. We sum the costs within each of the levels of the tree to obtain a set of pre-level costs
and then sum all pre-level costs to determine the total cost of all
levels of the recursion.

6. A Recursion Tree is best used to generate a good guess,

which can be verified by the Substitution Method.

example Consider T (n) = 2T + n2

Master Method

The Master Method is used for solving the following types of recurrence

T (n) = a T(n/b) + f (n) with a≥1 and b≥1 be constant & f(n) be a function and n/b can
be interpreted as

Let T (n) is defined on non-negative integers by the recurrence.

T (n) = a T(n/b)+ f (n)

In the function to the analysis of a recursive algorithm, the constants and function take
on the following significance:

n is the size of the problem.

a is the number of subproblems in the recursion.
n/b is the size of each subproblem. (Here it is assumed that all subproblems are
essentially the same size.)
f (n) is the sum of the work done outside the recursive calls, which includes the sum of
dividing the problem and the sum of combining the solutions to the subproblems.
It is not possible always bound the function according to the requirement, so we make
three cases which will tell us what kind of bound we can apply on the function.

Master Theorem:
It is possible to complete an asymptotic tight bound in these three cases:

Case1: If f (n) = for some constant ε >0, then it follows that:

T (n) = Θ

Case 2: If it is true, for some constant k ≥ 0 that:

F (n) = Θ then it follows that: T (n) = Θ

Case 3: If it is true f(n) = Ω for some constant ε >0 and it also true that: a

f for some constant c<1 for large value of n ,then :

T (n) = Θ((f (n))

Strassen’s Matrix Multiplication Algorithm
In this context, using Strassen’s Matrix multiplication algorithm, the time consumption
can be improved a little bit.
Strassen’s Matrix multiplication can be performed only on square
matrices where n is a power of 2. Order of both of the matrices are n × n.
Divide X, Y and Z into four (n/2)×(n/2) matrices as represented below −
Z=[IKJL]Z=[IJKL] X=[ACBD]X=[ABCD] and Y=[EGFH]Y=[EFGH]
Using Strassen’s Algorithm compute the following −
M1:=(A+C)×(E+F)M1:=(A+C)×(E+F)
M2:=(B+D)×(G+H)M2:=(B+D)×(G+H)
M3:=(A−D)×(E+H)M3:=(A−D)×(E+H)
M4:=A×(F−H)M4:=A×(F−H)
M5:=(C+D)×(E)M5:=(C+D)×(E)
M6:=(A+B)×(H)M6:=(A+B)×(H)
M7:=D×(G−E)M7:=D×(G−E)
Then,
I:=M2+M3−M6−M7I:=M2+M3−M6−M7
J:=M4+M6J:=M4+M6
K:=M5+M7K:=M5+M7
L:=M1−M3−M4−M5L:=M1−M3−M4−M5

Analysis

T(n)={c7xT(n2)+dxn2ifn=1otherwiseT(n)={cifn=17xT(n2)+dxn2otherwise wher
e c and d are constants
Using this recurrence relation, we get T(n)=O(nlog7)T(n)=O(nlog7)
Hence, the complexity of Strassen’s matrix multiplication algorithm
is O(nlog7)O(nlog7).