P20CAT1001
DATA STRUCTURES
AND ALGORITHMS
Department of Computer Applications
Analysis of Algorithm –
Efficiency
2
• Analysis of algorithm:
• An investigation of an algorithm’s efficiency with respect
to two resources:
• Running time
• Memory space
3
Two kinds of efficiency
• Time efficiency: indicates how fast an algorithm
runs
• Space efficiency: deals with the extra space the
algorithm requires
4
Measuring an input’s size
• Algorithms efficiency can be investigated as a
function of some parameter n indicating the
algorithm’s input size
5
Units for measuring running time:
Time efficiency is analyzed by determining the number of repetitions of the
basic operation as a function of input size
• Basic operation: the operation that contributes the most towards the
running time of the algorithm
• Steps:
• Identify the most important operation of the algorithm, called basic
operation
• Compute the number times the basic operation is executed
input size
T(n) ≈ copC(n)
running time execution time Number of times
for basic operation basic operation is
or cost executed 6
Orders of Growth
7
Orders of Growth
8
Type Notation Example Algorithms
Logarithmic O(log n) Binary Search
Linear O(n) Linear Search
Super linear O(n log n) Heap Sort, Merge Sort
Matrix Multiplication, Bubble Sort, Sélection Sort,
Polynomial O(n^c)
Insertion Sort, Bucket Sort
Exponential O(c^n) Tower of Hanoi
Brute force Search algorithm for Traveling Salesman
Factorial O(n!)
Problem
9
Worst case, best case and average case
efficiencies
• There are many algorithms for which running time
depends not only on an input size but also on the
specifics of a particular input.
• The running time of an algorithm can be different for
the same list size n.
10
Worst case, best case and average case
efficiencies
1. Worst-case efficiency of an algorithm is its
efficiency for the worst-case input of size n, which is
an input of size n for which the algorithm runs the
longest among all possible inputs of that size.
2. Best-case efficiency of an algorithm is its efficiency
for the best-case input of size n, which is an input of
size n for which the algorithm runs the fastest
among all possible inputs of that size.
3. Average-case efficiency provides the information
about an algorithm’s behavior on a typical or random
input. 11
Example
12
• Worst case:
• When there are no matching element S 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.
• Cworst(n) = n
• Best case:
• When the first matching element happens to be
the first one on the list
• The algorithm makes the smallest number of key
comparisons among all possible inputs of size n.
• Cbest(n) = 1
13
• Average case
• To analyze the algorithm’s average-case
efficiency, some assumptions about possible
inputs of size n has to be made
a) The probability of a successful search is p(0≤p ≤ 1)
b) The probability of the 1st match occurring in the ith
position of the list is the same for every i.
Cavg(n) = (n+1)/2, for a successful search
Cavg(n) = n, for an unsuccessful search
14
Algorithm Analysis
• Algorithm analysis is the process of evaluating the performance
of an algorithm in terms of time and space complexity.
• The goal is to estimate the efficiency of an algorithm and
understand its behavior as the input size grows.
• Three primary asymptotic notations are used for this purpose:
Big O, Big Theta, and Big Omega.
15
Big O Notation (O)
• Big O notation is a powerful tool used in computer science to describe the time
complexity or space complexity of algorithms.
• It provides a standardized way to compare the efficiency of different algorithms in
terms of their worst-case performance(The worst-case performance of an
algorithm refers to the scenario in which the algorithm performs the
least efficiently or takes the maximum amount of time or resources
among all possible input data.).
• It provides the worst-case scenario, ensuring that the algorithm will not perform
worse than a certain threshold as the input size grows.
• Big-O, commonly referred to as “Order of”, is a way to express the upper bound of
an algorithm’s time complexity
• Big-O notation is used to describe the performance or complexity of an algorithm.
Specifically, it describes the worst-case scenario in terms of time or space complexity.
16
Orders of Growth
17
Big O vs. Big Theta vs. Big Omega
Big O: This represents the worst-case performance for an algorithm, setting
an upper bound on how slow your code can be. It’s noted as O(n²).
Big Theta (Θ): This represents the average-case, typical case performance
for an algorithm. It’s noted as Θ(n×p).
Big Omega (Ω): This represents the best-case performance for an
algorithm, setting a lower bound on how fast the code can perform. It’s
noted as Ω(n).
18
Analyzing Searching Algorithms
Linear Search:
• Time Complexity: O(n)
• Space Complexity: O(1)
Binary Search:
• Time Complexity: O(log n)
• Space Complexity: O(1)
19
Analyzing Sorting Algorithms
Big-O
• Helps estimate performance for large inputs.
• Guides the choice of algorithms in real-world scenarios.
• Example: Sorting a list of 1,000,000 elements—O(n log n) is preferable over
O(n2)
nlog(n) = 9965.78, when n=1000 20
n2 =10,00,000, when n=1000
• x=5+(15*20) called O(1)
Independent of input Size
• If we have sequence of Statements
X= 5+(15*25);
Y=20-5;
Print (x+y)
Total time =O(1)+O(1)+O(1) =O(1)
• For x in range(0,n) //N
print (x)//O(1)
Total time = N*O(1)=O(N)
21
22
Big O Notation - Problems
Determine the Big O notation for the following functions:
a. f(n) = 5n + 3
b. f(n) = 3n^2 + 7n + 2
c. f(n) = log(n^3)
23
Big O Notation - Problems
24
Big O Notation - Problems
Determine the Big O notation for the following functions:
d. f(n) = n^3 + 2n^2 + 10
e. f(n) = 2^n + n^2
25
Big O Notation - Problems
26
Thank You
27
