Performance Analysis,Time complexity, Asymptotic Notations

Lecture Notes on
Design and Analysis of Algorithms
21CS42
Contents
1. Introduction
1.1. What is an Algorithm?
1.2. Algorithm Specification
1.3. Analysis Framework
2. Performance Analysis
2.1. Space complexity
2.2. Time complexity
3. Asymptotic Notations
3.1. Big-Oh notation
3.2. Omega notation
3.3. Theta notation
3.4. Little-oh notation
3.5. Basic symptotic notations
3.6. Mathematical analysis of Recursive and non-recursive algorithm
4. Brute force design technique:
4.1. Selection sort
4.2. Sequential search
4.3. String matching algorithm with complexity Analysis.
Module-1: Introduction to Algorithm

1.1Introduction
Module-1: Introduction
1.1.1 What is an Algorithm?
Algorithm: An algorithm is a finite sequence of unambiguous instructions to solve a particular
problem.
a. Input. Zero or more quantities are externally supplied.
b. Output. At least one quantity is produced.
c. Definiteness. Each instruction is clear and unambiguous. It must be perfectly clear what
should be done.
d. Finiteness. If we trace out the instruction of an algorithm, then for all cases, the algorithm
terminates after a finite number of steps.
e. Effectiveness. Every instruction must be very basic so that it can be carried out, in principle,
by a person using only pencil and paper. It is not enough that each operation be definite as in
criterion c; it also must be feasible.
1.1.2. Algorithm Specification
An algorithm can be specified in
1) Simple English
2) Graphical representation like flow chart
3) Programming language like C++/java
4) Combination of above methods.
Example: Combination of simple English and C++, the algorithm for selection sort is specified as
follows.
Example: In C++ the same algorithm can be specified as follows. Here Type is a basic or user
defined data type.

1.1.3. Analysis Framework
Measuring an Input’s Size
It is observed that almost all algorithms run longer on larger inputs. For example, it takes longer to
sort larger arrays, multiply larger matrices, and so on. Therefore, it is logical to investigate an
algorithm's efficiency as a function of some parameter n indicating the algorithm's input size.
There are situations, where the choice of a parameter indicating an input size does matter. 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 the 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:= log2 n ] + 1.
This metric usually gives a better idea about the efficiency of algorithms in question.
Units for Measuring Running lime
To measure an algorithm's efficiency, we would like to 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 xecuted. This approach is both excessively difficult and, as we shall see, usually
unnecessary. The thing to do 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.
For example, most sorting algorithms work by comparing elements (keys) of a list being sorted with
each other; for such algorithms, the basic operation is a key comparison.
As another example, algorithms for matrix multiplication and polynomial evaluation require two
arithmetic operations: multiplication and addition.
Let cop be the execution time of an algorithm's basic operation on a particular computer, and let C(n) be
the number of times this operation needs to be executed for this algorithm. Then we can estimate the
running time T(n) of a program implementing this algorithm on that computer by the formula:
𝑇(𝑛) ≈ 𝑐𝑜𝑝𝐶(𝑛)
Unless n is extremely large or very small, the formula can give a reasonable estimate of the algorithm's
running time.
It is for these reasons that the efficiency analysis framework ignores multiplicative constants and
concentrates on the count's order of growth to within a constant multiple for large-size inputs.

Orders of Growth
Why this emphasis on the count's order of growth for large input sizes? Because for large values of n, it
is the function's order of growth that counts: just look at table which contains values of a few functions
particularly important for analysis of algorithms.
Table: Values of several functions important for analysis of algorithms
Algorithms that require an exponential number of operations are practical for solving only problems of
very small sizes.
1.2. Performance Analysis
There are two kinds of efficiency: time efficiency and space efficiency.
● Time efficiency indicates how fast an algorithm in question runs;
● Space efficiency deals with the extra space the algorithm requires.
In the early days of electronic computing, both resources time and space were at a premium. The
research experience has shown that for most problems, we can achieve much more spectacular progress
in speed than inspace. Therefore, we primarily concentrate on time efficiency.
1.2.1 Space complexity
Total amount of computer memory required by an algorithm to complete its execution is called as space
complexity of that algorithm. The Space required by an algorithm is the sum of following components
● A fixed part that is independent of the input and output. This includes memory space for codes,
variables, constants and so on.
● A variable part that depends on the input, output and recursion stack. ( We call these
parameters as instance characteristics)
Space requirement S(P) of an algorithm P, S(P) = c + Sp where c is a constant depends on the fixed
part, Sp is the instance characteristics
Example-1: Consider following algorithm abc()
Here fixed component depends on the size of a, b and c. Also instance characteristics Sp=0

Example-2: Let us consider the algorithm to find sum of array. For the algorithm given here the
problem instances are characterized by n, the number of elements to be summed. The space needed by
a[ ]depends on n.So the space complexity can be written as;Ssum(n) ≥ (n+3); n for a[ ], One each for
n, i and s.
1.2.2 Time complexity
Usually, the execution time or run-time of the program is refereed as its time complexity denoted by
tp(instance characteristics). This is the sum of the time taken to execute all instructions in the program.
Exact estimation runtime is a complex task, as the number of instructions executed is dependent on the
input data. Also different instructions will take different time to execute. So for the estimation of the
time complexity we count only the number of program steps. We can determine the steps needed
by a program to solve a particular problem instance in two ways.
Method-1: We introduce a new variable count to the program which is initialized to zero. We also
introduce statements to increment count by an appropriate amount into the program. So when each
time original program executes, the count also incremented by the step count.
Example: Consider the algori hm sum(). After the introduction of the count the program will be as
follows. We can estimate that invocation of sum() executes total number of 2n+3 steps.
Method-2: Determine the step count of an algorithm by building a table in which we list the total
number of steps contributed by each statement. An example is shown below. The code will find the sum
of n numbers.
Example: Matrix addition

The above method is both excessively difficult and, usually unnecessary. The thing to do is to identify the most
important operation contributing the m operation of the algorithm, called the basic operation, the st to the total
running time, and compute the number of times the basic operation is executed.
Trade-off
There is often a time-space-tradeoff involved in a problem, that is, it cannot be solved with few
computing time and low memory consumption. One has to make a compromise and to exchange
computing time for memory consumption or vice versa, depending on which algorithm one chooses
and how one parameterizes it.
1.3. Asymptotic Notations
The efficiency analysis framework concentrates on the order of growth of an algorithm’s basic operation count
as the principal indicator of the algorithm’s efficiency. To compare and rank such orders of growth, computer
scientists use three notations: O(big oh), Ω(big omega), Θ (big theta) and o(little oh)
1.3.1. Big-Oh notation
Definition: A function t(n) is said to be in O(g(n)),
denoted t(n)∈O(g(n)), if t (n) is bounded above by
some constant multiple of g(n) for all large n, i.e., if
there exist some positive constant c and some
nonnegative integer n0 such that
t(n) ≤ cg(n) for all n ≥ n0.
Informally, O(g(n)) is the set of all functions with a lower or same order of growth as g(n). Note
that the definition gives us a lot of freedom in choosing specific valuesfor constants c and n0.
Examples: 𝑛 є (𝑛2), 100𝑛 + 5 є (𝑛2), 1 (𝑛 − 1)є𝑂(𝑛2)
2
𝑛3 ∉ (𝑛2), 0.00001𝑛3 ∉ (𝑛2), 𝑛4 + 𝑛 + 1 ∉ (𝑛2)

Strategies to prove Big-O: Sometimes the easiest way to prove that f (n) = O(g(n)) is to take c to
be the sum of the positive coefficients off(n). We can usually ignore the negative coefficients.
Example: To prove 100n + 5 ∈ O(n2
)
100n + 5 ≤ 105n2
. (c=105, n0=1)
Example: To prove n2
+ n = O(n3
)
Take c = 1+1=2, if n ≥n0=1, then n2
+ n
= O(n3
)
i) Prove 3n+2=O(n) ii) Prove 1000n2
+100n-6 = O(n2
)
1.3.2. Omega notation
Definition: A function t(n) is said to be in Ω(g(n)),
denoted t(n)∈Ω(g(n)), if t(n) is bounded below by
some positive constant multiple of g(n) for all large
n,i.e., if there exist some positive constant c and some
nonnegative integer n0 suchthatt(n) ≥ c g(n) for
all n ≥ n0.
Here is an example of the formal proof that n3
∈Ω(n2
):n3
≥ n2
for all n ≥ 0, i.e., we
can select c = 1 and n0 = 0.
Example:
Example: To prove n3
+ 4n2
= Ω(n2
)
We see that, if n≥0, n3
+4n2
≥ n3
≥ n2;
Therefore n3
+4n2
≥ 1n2
for
alln≥0 Thus, we have shown that n3
+4n2
=Ω(n2
) where c = 1 &
n0=0
1.3.3. Theta notation
A function t(n) is said to be in Θ(g(n)), denoted t(n)
∈ Θ(g(n)),if t (n) is bounded both above and below
by some positive constant multiples ofg(n)
for all large n, i.e., if there exist some positive
constants c1 and c2 and somenonnegative integer n0
such that
c2g(n) ≤ t(n) ≤c1g(n) for all n ≥ n0.

Example: n2
+ 5n + 7 = Θ(n2
)
Strategies for Ω and Θ
● Proving that a f(n) = Ω(g(n)) often requires more thought.
– Quite often, we have to pick c < 1.
– A good strategy is to pick a value of c which you think will work, and determine
which value of n0 is needed.
– Being able to do a little algebra helps.
– We can sometimes simplify by
ignoring terms of f(n) coefficients.
with the positive
● The following theorem shows us that proving f(n) = Θ(g(n)) is nothing new:
Theorem: f(n) = Θ(g(n)) if and only iff(n) = O(g(n)) and f(n) = Ω(g(n)).
Thus, we just apply the previous two strategies.

Theorem: If t1(n) ∈O(g1(n)) and t2(n) ∈O(g2(n)), then t1(n) + t2(n) ∈O(max{g1(n), g2(n)}). (The
analogous assertions are true for the Ω and Ө notations as well.)
Proof: The proof extends to orders of growth the following simple fact aboutfour arbitrary real numbers
a1, b1, a2, b2: if a1 ≤ b1 and a2 ≤ b2, then a1 + a2 ≤ 2 max{b1, b2}.
Since t1(n) ∈O(g1(n)), there exist some positive constant c1 and some nonnegative integer n1 such that
t1(n) ≤ c1g1(n) for all n ≥ n1.
Similarly, since t2(n) ∈O(g2(n)), t2(n) ≤ c2g2(n) for all n ≥ n2.
Let us denote c3 = max{c1, c2} and consider n>=max{n1,n2} so that
we can use both inequalities. Adding them yields the following: t1(n) + t2(n) ≤ c1g1(n) + c2g2(n)
≤ c3 g1(n) + c3g2(n) = c3[g1(n) + g2(n)]
≤ c32 max{g1(n), g2(n)}.
Hence, t1(n) + t2(n) ∈ O(max{g1(n), g2(n)}), with the constants c and n0 required by the O
definition being 2c3 = 2 max{c1, c2} and max{n1, n2}, respectively.
3.4. Little Oh The function f(n)= o(g(n)) [ i.e f of n is a little oh of g of n ] if and only if
lim ƒ(𝑛) = 0
𝑛→∞ 𝑔(𝑛)
For comparing the order of growth limit is used
If the case-1 holds good in the above limit, we represent it by little-oh.
Example:

1.3.5. Basic asymptotic efficiency Classes
Class Name Comments

1.3.6. Mathematical Analysis of Non-recursive & Recursive Algorithms
Analysis of Non-recursive Algorithms
General Plan for Analyzing the Time Efficiency of Nonrecursive Algorithms
1. Decide on a parameter (or parameters) indicating an input’s size.
2. Identify the algorithm’s basic operation. (As a rule, it is located in innermost loop.)
3. Check whether the number of times the basic operation is execut d depends only on the size of
an input. If it also depends on some additional property, the worst-case, average-case, and, if
separately.
4. Set up a sum expressing the number of times the algorithm’s executed.
5. Using standard formulas and rules of sum manipulation, either
Example-1: To find maximum element in the given array
Here comparison is the basic operation. Note that number of comparisions will be same for all
arrays of size n. Therefore, no need to distinguish worst, best and average cases. Total number of
basic operations are,
Example-2: To check whether all the elements in the given array are distinct

2
Here basic operation is comparison. The maximum no. of comparisons happens in the worst case. i.e.
all the elements in the array are distinct and algorithms return true).
Total number of basic operations (comparison) in the worst case are,
Other than the worst case, the total comparisons areless than 1 𝑛2. For example if the first two elements
of the array are equal, only one comparison is computed. So in general C(n) =O(n2
)
Example-3: To perform matrix multiplication
Number of basic operations (multiplications) is
Total running time:
Suppose if we take into account of addition; Algoritham also have same number of additions
A(n) = n3
Total running time:

Example-4: To count the bits in the binary representation
The basic operation is count=count + 1 repeats no. of times
Analysis of Recursive Algorithms
General plan for analyzing the time efficiency of recursive algorithms
1. Decide on a parameter (or parameters) indicating an input’s size.
2. Identify the algorithm’s basic operation.
3. Check whether the number of times the basic operation is executed can varyon different inputs of the same
size; if it can, the worst-case, average-case, and best-case efficiencies must be investigated separately. Set
up a recurrence relation, with an appropriate initial condition, for the number of times the basic operation
is executed.
4. Solve the recurrence or, at least, ascertain the order of growth of its solution.
Since the function F(n) is computed according to the formula
The number of multiplicationsM(n) needed to compute it must satisfy the equality
Such equations are called recurrence relations
Example-1

Condition that makes the algorithm stopif n = 0 return 1. Thus recurrence relation and initial
conditionfor the algorithm’s number of multiplications M(n) can be stated as
We can use backward substitutions method to solve this
….
Example-2: Tower of Hanoi puzzle. In this puzzle, There are n disks of different sizes that canslide
onto any of three pegs. Initially, all the disks are on the first peg in order ofsize, the largest on the bottom
and the smallest on top. The goal is to move all thedisks to the third peg, using the second one as an
auxiliary, if necessary. We canmove only one disk at a time, and it is forbidden to place a larger disk on
top of asmaller one.The problem has an elegant recursive solution, which is illustrated in Figure.
1. If n = 1, we move the single disk directly from the source peg to the destination peg.
2. To move n>1 disks from peg 1 to peg 3 (with peg 2 as auxiliary),
o we first move recursively n-1 disks from peg 1 to peg 2 (with peg 3 as auxiliary),
o then move the largest disk directly from peg 1 to peg 3, and,
o finally, move recursively n-1 disks from peg 2 to peg 3 (using peg 1 as auxiliary).
Figure: Recursive solution to the Tower of Hanoi puzzle
Algorithm: TowerOfHanoi(n, source, dest, aux)
If n == 1, THEN
move disk from
source to dest else
TowerOfHanoi (n - 1, source, aux, dest)
move disk from source to dest
TowerOfHanoi (n - 1, aux, dest, source)
End if

Computation of Number of Moves
The number of moves M(n) depends only on n. The recurrence equation is
We have the following recurrence relation for the number of moves M(n):
We solve this recurrence by t e same method of backward substitutions:
The pattern of the first three sums on the left suggests that the next one will be
24
M(n − 4) + 23
+ 22
+ 2 + 1, and generally, after i substitutions, we get
Since the initial condition is specified for n = 1, which is achieved for i = n-1, we get the
following formula for the solution to recurrence,
Example-3: To count bits of a decimal number in its binary representation
The recurrence relation can be written as
Also note that A(1) = 0.
.
The standard approach to solving such a recurrence is to solve it only for n = 2k
and then take
advantage of the theorem called the smoothness rule which claims that under very broad
assumptions the order of growth observed for n = 2k
gives a correct answer about the order of
growth for all values of n.

1.4. Brute force design technique:
Brute force is straight forward approach to solving a problem, usually directly based on the
problem statement and definitions of the concepts involved.
1.4.1 Selection sort
We start selection sort by scanning the entire given list to find its smallest element and exchange it with
the first element, putting the smallest element in its final position in the sorted list. Then we scan the list, starting
with the second element, putting the second smallest element in its final position. Generally, on the ith pass
through the list, which we number from 0 to n-2, the algorithm searches for the last n-I elements and swaps it with
Ai:
A0 ≤ A1 ≤ …… ≤Ai-1 | Ai…….Amin ….. An-1
in their final positions the last n-i elements
After n-1 passes, the list is sorted.
The number of times the algorithm executed depends only on the array’s size and is given by
After solving using summation formulas
Thus selection sort has a Θ(n2) time complexity.
1.4.2 Sequential search
This is also called as Linear search. Here we start from the initial element of the array and compare it with the
search key. We repeat the same with all the elements of the array till we encounter the search key or till we reach
end of the array.

The time efficiency in worst case is O(n), where n is the number of elements of the array. In best case it is O(1), it
means the very first element is the search key.
1.4.3 String matching algorithm with complexity Analysis
Another example of Brute force approach is string matching, where string of n characters called text and a string
of m characters (m<=n) called the pattern is given. Here job is to find whether the pattern is present in text or not.
If we want to find i-the index of the leftmost character of the first matching substring in the
We start matching with the very first character, if a match then only j is incremented and again compared with next
character of both the strings. If not then I is incremented and j starts from beginning of pattern string. If pattern
found we return the position from where the pattern began. Pattern is tried to match till n-m elements, later we
need not try to match as the elements will be lesser than pattern. If it doesn’t match by n-m elements then pattern is
not matched.
The worst case is Θ(nm). Best case is Θ(m).

Performance Analysis,Time complexity, Asymptotic Notations

Recommended

More Related Content

Similar to Performance Analysis,Time complexity, Asymptotic Notations (20)

More from DrSMeenakshiSundaram1 (6)

Recently uploaded (20)

Performance Analysis,Time complexity, Asymptotic Notations