19CSE212: Data Structures & Algorithms

Lecture 2 : Complexity Analysis

Ritwik M

Based on the reference materials by Prof. Goodrich, OCW METU and Dr. Vidhya Balasubramanian

1 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 Analysis of Data Structures

• Data structures have many functions

̶ Each function is a set of simple instructions
• Analysis
̶ Determine resources, time and space the algorithms requires
• Goal
̶ Estimate time required to execute the functionalities
̶ Reduce the running time of the program
̶ Understand the space occupied by the data structure

2 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 Issues in Analysis

• Running time grows with input size

̶ Varies with different inputs
̶ Actual running time can be calculated in seconds or milliseconds
• Issues
̶ The system setup must be same for all inputs
̶ Same hardware and software must be used
̶ Actual time maybe affected by other programs running on the same
machine
• A theoretical analysis is sometimes preferable

3 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 Average Case and Worst Case

• The running time and memory usage of a program is not

constant
̶ Depends on input
̶ Can run fast for certain inputs and slow for others
o e.g linear search
• Average Case Cost
̶ Cost of the algorithm (time and space) on average
̶ Difficult to calculate
• Worst Case
̶ Gives an upper limit for the running time and memory usage
̶ Easier to analyze the worst case

4 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 Method for analyzing complexity

• Model of Computation
̶ Mathematical Framework
• Asymptotic Notation
̶ What to Analyze
• Running Time Calculations
• Checking the analysis

5 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 Counting Primitives to analyze time complexity

• Primitive operations are identified and counted to analyze cost

• Primitive Operations
̶ Assigning a value to a variable What about an IF -Then
̶ Performing an arithmetic operation -Else Statement?

̶ Calling a method
̶ Comparing two numbers
̶ Indexing into an array
̶ Following an object reference
̶ Returning from a method

6 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 Example
Algorithm FindMax(S, n)
Input : An array S storing n numbers, n>=1
Output: Max Element in S
curMax <-- S[0] (2 operations)
i ← 0 (1 operations)
while i< n-1 do (n comparison operations)
if curMax <A[i] then (2(n-1) operations)
curMax <-- A[i] (2(n-1) operations)
i ← i+1; (2 (n-1) operations)
return curmax (1 operations)
Complexity between 5n and 7n-2

7 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 Some

• Loops
̶ cost is linear in terms of number of iterations
̶ Nested loops – product of iteration of the loops
o If outer loop has n iterations, and inner m, cost is mn

̶ Multiple loops not nested

o Complexity proportional to the longest running loop

• If Else
̶ Cost of if part of else part whichever is higher

8 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 Exercises

1) sum = 0; 4) for (i = 20; i <= 30; i++) {

for( i=0; i<n; i++ ) for (j=1; j<=n; j+
sum++; +){
x = x + 1;
2) sum = 0;
}
for( i=0; i<n; i++ )
}
for( j=0; j<n; j++ )
sum++;
3) sum = 0;
for( i=0; i<n; i++ )
for( j=0; j<n*n; j+
+)
sum++;

9 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 Growth Rates and Complexity

• Important factor to be considered when estimating complexity

• When experimental setup (hardware/software) changes
̶ Running time/memory is affected by a constant factor
̶ 2n or 3n or 100n is still linear
̶ Growth rate of the running time/memory is not affected
• Growth rates of functions
̶ Linear
̶ Quadratic
̶ Exponential

10 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 Comparing Growth Rates

11 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 Ideal Logic / From the Growth Rates

• Data structure operations to run in times proportional to the

constant or logarithm function
• Algorithms to run in linear or n-log-n time

12 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 Asymptotic Analysis

• Can be defined as a method of describing limiting behavior

• Used for determining the computational complexity of
algorithms
̶ A way of expressing the main component of the cost of an algorithm
using the most determining factor
̶ e.g if the running time is 5n2+5n+3, the most dominating factor is 5n2
• Capturing this dominating factor is the purpose of asymptotic
notations

13 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 Big-Oh Notation

• Given a function f(n) we say, f(n) is O(g(n)) if there are positive

constants c and n0 such that f(n)<= cg (n) when n>= n0

14 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 Big-Oh Example
• Show 7n-2 is O(n) – [Hint: prove that f(n)<=cg(n)]
̶ need c > 0 and n0 >= 1 such that 7n-2 <= cn for n >= n0
̶ this is true for c =7 and n0 = 1
• Show 3n3 + 20n2 + 5 is O(n3)
̶ need c > 0 and n0 >= 1 such that 3n3 + 20n2 + 5 <= cn3 for n >= n0
̶ this is true for c = 4 and n0 = 21
• n2 is not O(n)
̶ Must prove n2 <= cn
̶ n <= c
̶ The above inequality cannot be satisfied since c must be a constant
̶ Hence proof by contradiction

15 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 Big-Oh Significance

• The big-Oh notation gives an upper bound on the growth rate

of a function
• The statement “f(n) is O(g(n))” means that the growth rate of
f(n) is not more than the growth rate of g(n)
̶ We are guaranteeing that f(n) grows at a rate no faster than g(n)
̶ Both can grow at the same rate
̶ Though 1000n is larger than n2, n2 grows at a faster rate
o n2 will be larger function after n = 1000
o Hence 1000n = O(n2)

• The big-Oh notation can be used to rank functions according to

their growth rate

16 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 Big-Oh Significance

• Table of max-size of a problem that can be solved in one

second, one minute and one hour for various running time
measures in microseconds [Goodrich]

17 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 • Take away from the table
̶ Algorithms with quadratic or cubic running times are less practical, and
algorithms with exponential running times are infeasible for all but the
smallest sized inputs

18 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 Common Rules for Big-Oh

• If is f(n) a polynomial of degree d, then f(n) is O(nd), i.e.,

̶ Drop lower-order terms
̶ Drop constant factors
• Use the smallest possible class of functions to represent in big
Oh
̶ “2n is O(n)” instead of “2n is O(n2)”
• Use the simplest expression of the class
̶ “3n+ 5 is O(n)” instead of “3n + 5 is O(3n)”

19 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 Exercises

• Show that 8n+5 is O(n)

• Show that 20n3 +10nlogn+5 is O(n3)
• Show that 3logn+2 is O(logn).

20 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 Try This Out

• Consider a set of numbers from 1 to n. All the values except

one value are present
̶ Goal: Find the missing number
̶ Give 3 solutions to find the missing number
̶ What is the time and space complexity in terms of n?

21 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 Exercise

• Algorithm arrayFind(x,A);
//Given an element x and an n element array A, output pos if present in A
for i = 0 to n-1 do
if x = A[i] then
return I
return -1
• There is an algorithm find2D to find an element x in an nxn
array A. The algorithm iterates over the rows of A and calls the
algorithm arrayFind on each one, until x is found or it has
searched all rows of A.
̶What is the time and space complexity of the algorithm

22 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 More Exercises

• Calculate the value returned by total

def example4(S):
”””Return the sum of the prefix sums of sequence S.”””
n = len(S)
prefix = 0
total = 0
for j in range(n):
prefix += S[j]
total += prefix
return total

23 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering
 Even More Exercises

• Given an n-element sequence S, Algorithm D calls Algorithm E

on each element S[i]. Algorithm E runs in O(i) time when it is
called on element S[i]. What is the worst-case running time of
Algorithm D?
• A sequence S contains n−1 unique integers in the range
[0,n−1], that is, there is one number from this range that is not
in S. Design an O(n)-time algorithm for finding that number.
You are only allowed to use O(1) additional space besides the
sequence S itself.

24 Amrita Vishwa Vidhyapeetham Ritwik M

Amrita School of Engineering