Algorithm Analysis

Courtesy: Md. Manowarul Islam, Asst. Prof., Dept. of CSE, JnU.

 Introduction
● Data structures
● Methods of organizing data in order to facilitate access and
modification.
● What is Algorithm?
● a clearly specified set of simple instructions on the data to be
followed to solve a problem
📂 Takes a set of values, as input and
📂 produces a value, or set of values, as output
● May be specified
📂 In English
📂 As a computer program
📂 As a pseudo-code
● Program = data structures + algorithms
 Introduction
● Why need algorithm analysis ?
● writing a working program is not good enough
● The program may be inefficient!
● If the program is run on a large data set, then the
running time becomes an issue
 Introduction
● Suppose we have a problem P1 to solve
● We have many algorithms.

● Which one of the above algorithms will choose?

●Analyzing an algorithm
●Predicting
the resources that the algorithm requires
●Resources include
●Memory
●Computational time (usually most important)
 Example: Selection Problem
● Given a list of N numbers, determine the kth
largest, where k ≤ N.
● Algorithm 1:
(1) Read N numbers into an array
(2) Sort the array in decreasing order by some
simple algorithm
(3) Return the element in position k
● Algorithm 2:
(1) Read the first k elements into an array and sort
them in decreasing order
(2) Each remaining element is read one by one
📂 If smaller than the kth element, then it is ignored
📂 Otherwise, it is placed in its correct spot in the array,
bumping one element out of the array.
(3) The element in the kth position is returned as the
answer.
● Which algorithm is better when
● N =100 and k = 100?
● N =100 and k = 1?

● What happens when

● N = 1,000,000 and k = 500,000?
● We come back after sorting analysis, and there exist
better algorithms
 Algorithm Analysis
● We only analyze correct algorithms
● An algorithm is correct
● If, for every input instance, it halts with the correct output
● Incorrect algorithms
● Might not halt at all on some input instances
● Might halt with other than the desired answer

● Analyzing an algorithm
● Predicting the resources that the algorithm requires
● Resources include
📂 Memory
📂 Computational time (usually most important)
● Factors affecting the running time
● computer
● compiler
● algorithm used
● input to the algorithm
📂 The content of the input affects the running time
📂 typically, the input size (number of items in the input) is the main
consideration
● E.g. sorting problem ⇒ the number of items to be sorted
● E.g. multiply two matrices together ⇒ the total number of
elements in the two matrices
● Machine model assumed
● Instructions are executed one after another, with no
concurrent operations ⇒ Not parallel computers
 Example
● Calculate

1
1
2 2N+2
3 4N
4 1

● Lines 1 and 4 count for one unit each

● Line 3: executed N times, each time four units
● Line 2: (1 for initialization, N+1 for all the tests, N for
all the increments) total 2N + 2
● total cost: 6N + 4 ⇒ O(N)
 Time Complexity
● For most of the algorithms associated with this
course, time complexity comparisons are
more interesting than space complexity
comparisons
● Time complexity: A measure of the amount of
time required to execute an algorithm

13-11
 Time Complexity
● Factors that should not affect time complexity
analysis:
● The programming language chosen to implement
the algorithm
● The quality of the compiler
● The speed of the computer on which the algorithm
is to be executed

13-12
 Time Complexity
● Analysis is based on the amount of work done
by the algorithm
● Time complexity expresses the relationship
between the size of the input and the run time
for the algorithm
● Usually expressed as a proportionality, rather
than an exact function

13-13
Why should we care????
 Let see….
● Suppose Rahim and Karim are two students
and they both have given a same assigmnet.
● Determine whether a number n is prime or not.
● Example of prime numbers: 2,3,5,7
 Let see….
● Rahim ● Karim

N-1 divisions √N-1 divisions

● Both the algorithms will give the right answer

● But for a large value of n , Rahim’s program

will run for several days!!!!!!!!

 Let see….
● Rahim ● Karim

N-1 divisions √N-1 divisions

● Lets assume, the computer takes 1 ms for a division

 Let see….
● Rahim ● Karim

n-1 divisions √n-1 divisions

● Lets assume, the computer takes 1 ms for a division

input Algorithm-1 Algorithm-2

n=11(pirme numbers) 9 ms 2 ms
 Let see….
● Rahim ● Karim

n-1 divisions √n-1 divisions

● Lets assume, the computer takes 1 ms for a division

input Algorithm-1 Algorithm-2

n=11(pirme numbers) 9 ms 2 ms
n=101 99ms 9 ms
 Let see….
● Rahim ● Karim

n-1 divisions √n-1 divisions

● Lets assume, the computer takes 1 ms for a division

input Algorithm-1 Algorithm-2

n=11(pirme numbers) 9 ms 2 ms
n=101 99ms 9 ms
n=1000003=106+3 ≈106 ms =103sec √(106+3)-1 ≈103ms
≈16.6 mins ≈1 sec
 Let see….
● Rahim ● Karim

n-1 divisions √n-1 divisions

input Algorithm-1 Algorithm-2
n=11(pirme numbers) 9 ms 2 ms
n=101 99ms 9 ms
n=1000003=106+3 ≈106 ms =103sec √(106+3)-1 ≈103ms
≈16.6 mins ≈1 sec
n=10000000019 ≈1010ms=107 sec ≈105ms=100sec
≈115 days ≈1.66 mins
 Let see….
● Rahim ● Karim

n-1 divisions √n-1 divisions

input Algorithm-1 Algorithm-1
n=11(pirme numbers) 9 ms 2 ms
n=101 99ms 9 ms
n=1000003=106+3 ≈106 ms =103sec √(106+3)-1 ≈103ms
≈16.6 mins ≈1 sec
n=10000000019 ≈1010ms=107 sec ≈105ms=100sec
≈115 days ≈1.66 mins
 Typical Running Time Functions
● 1 (constant running time):
● Instructions are executed once or a few times
● logN (logarithmic)
● A big problem is solved by cutting the original problem in
smaller sizes, by a constant fraction at each step
● N (linear)
● A small amount of processing is done on each input element
● N logN
● A problem is solved by dividing it into smaller problems,
solving them independently and combining the solution
 Typical Running Time Functions
● N2 (quadratic)
● Typical for algorithms that process all pairs of data items
(double nested loops)

● N3 (cubic)
● Processing of triples of data (triple nested loops)

● NK (polynomial)
● 2N (exponential)
● Few exponential algorithms are appropriate for practical use
Growth of Functions

25
Complexity Graphs

log(n)
Complexity Graphs

n log(n)

log(n)
Complexity Graphs

n10 n3

n2
n log(n)
Complexity Graphs (log scale)
3n
nn
n20

2n

n10

1.1n
 Running-time of algorithms
● Bounds are for the algorithms, rather than programs
● programs are just implementations of an algorithm, and
almost always the details of the program do not affect the
bounds

● Algorithms are often written in pseudo-codes

● We use ‘almost’ something like C/C++.

● Bounds are for algorithms, rather than problems

● A problem can be solved with several algorithms, some are
more efficient than others
 Introduction
Why are asymptotic notations important?

● They give a simple characterization of an algorithm’s efficiency.

● They allow the comparison of the performances of various

algorithms.

● For large values of components/inputs, the multiplicative constants

and lower order terms of an exact running time are dominated by
the effects of the input size (the number of components).
 Algorithm Complexity
● Worst Case Complexity:
● the function defined by the maximum number of
steps taken on any instance of size n
● Best Case Complexity:
● the function defined by the minimum number of
steps taken on any instance of size n
● Average Case Complexity:
● the function defined by the average number of
steps taken on any instance of size n
 Worst- / average- / best-case
● Worst-case running time of an algorithm
● The longest running time for any input of size n
● An upper bound on the running time for any input
⇒ guarantee that the algorithm will never take longer
● Example: Sort a set of numbers in increasing order; and the
data is in decreasing order
● The worst case can occur fairly often
📂 E.g. in searching a database for a particular piece of information
● Best-case running time
● sort a set of numbers in increasing order; and the data is
already in increasing order
● Average-case running time
● May be difficult to define what “average” means
 Doing the Analysis
● It’s hard to estimate the running time exactly
● Best case depends on the input
● Average case is difficult to compute
● So we usually focus on worst case analysis
📂 Easier to compute
📂 Usually close to the actual running time
● Strategy: find a function (an equation) that, for large n, is an
upper bound to the actual function (actual number of steps,
memory usage, etc.)

Upper bound
Actual function
Lower bound
 Asymptotic notations

● Upper bound O(g(N))

● Lower bound Ω(g(N))
● Tight bound Θ(g(N))
 Big - O
● Definition:
if there exist constants c>0 and
n0 such that for all n>n0,
 Big - O

● if we can prove that

● for constant c and n0 where
● c≥0 and n ≥1
0

● Then we can say

C n f(n)=3n+2 c.g(n)=c.n
Example: 1 4 1 5 4
Lets say f(n)=3n+2 and g(n)=n
4 2 8 8
We have to prove:
4 3 11 12
-f(n) ≤ cg(n)
4 5 17 20
- 3n+2 ≤c.n
 Big - O
Example: 1
Lets say f(n)=3n+2 and g(n)=n
We have to prove:
-f(n) ≤ cg(n)
- 3n+2 ≤c.n

Example: 1
So we can say:
for c=4 and for all n≥2
f(n) ≤ cg(n)
C n f(n)=3n+2 c.g(n)=c.n
4 1 5 4
4 2 8 8
4 3 11 12
4 5 17 20
 Big - O
● In other words, g(n) bounds f(n) from above (for large
n’s) up to a constant.
● Examples:
 Common time complexities
●BETTER
● O(1) constant time
● O(log n) log time
● O(n) linear time
● O(n log n) log linear time
● O(n2) quadratic time
● O(n3) cubic time
● O(2n) exponential time
●WORSE

41
 Big-O Analysis in General
● Examples of dominant terms:
● n dominates log2(n)
● n*log2(n) dominates n
● n2 dominates n*log2(n)
● nm dominates nk when m > k
● an dominates nm for any a > 1 and m >= 0

• That is, log2(n) < n < n*log2(n) < n2 <

… < nm < an for a >= 1 and m > 2
13-42
 Big Oh: more examples
● N2 / 2 – 3N = O(N2)
● 1 + 4N = O(N)
● 7N2 + 10N + 3 = O(N2)
● log10 N = log2 N / log2 10 = O(log2 N) = O(log N)
● sin N = O(1); 10 = O(1), 1010 = O(1)
●

● log N + N = O(N)
 O(1) constant
● Algorithms whose solutions are independent
of the size of the problem’s inputs are said to
have constant time complexity
● Constant time complexity is denoted as O(1)
 O(1) constant
● retrieve, replace, and swap operations in array
are O(1): array indexing allows direct access
to an array location, independent of the array
size; no shifting occurs
● All operations in stack are O(1), provided that the tail
of the list is the top of the stack
 O(n)
● Loops
● at most the running time of the statements inside the for-loop
(including tests) times the number of iterations.
● O(N)
 2
O(n )
● Nested loops

● the running time of the statement multiplied by the product of

the sizes of all the for-loops.
● O(N2)
 2
O(n )
int x = 0;
for ( int j = 1; j <= n/2; j++ )
for ( int k = 1; k <= n*n; k++ )
x = x + j + k;

●Outer loop executes n/2 times.

●For each of those times, inner loop executes n2 times,
●so the body of the inner loop is executed (n/2)*n2 = n3/2 times.
●The algorithm is O(n3) .
 2
O(n )
int x = 0;
for ( int j = 1; j <= n; j++ )
for ( int k = 1; k < 3*j; k++ )
x = x + j;

• When j is 1, inner loop executes 3 times;

• when j is 2, inner loop executes 3*2 times; …
• when j is n, inner loop executes 3*n times.
• In all the inner loop executes 3+6+9+…+3n = 3(1+2+3+…+n)
= 3n2/2 + 3n/2 times.
•The algorithm is O(n2).
● Consecutive statements
● These just add
● O(N) + O(N2) = O(N2)

● Conditional: If S1 else S2
● never more than the running time of the test plus the larger of
the running times of S1 and S2.
● O(1)
 Analyzing Algorithms
● Predict the amount of resources required:
• memory: how much space is needed?

• computational time: how fast the algorithm runs?

● FACT: running time grows with the size of the input

● Input size (number of elements in the input)
● Size of an array, polynomial degree, # of elements in a matrix, # of bits in
the binary representation of the input, vertices and edges in a graph

Def: Running time = the number of primitive operations (steps) executed before
termination
● Arithmetic operations (+, -, *), data movement, control, decision making
(if, while), comparison
51
 Algorithm Complexity
● Worst Case Complexity:
● the function defined by the maximum number of
steps taken on any instance of size n
● Best Case Complexity:
● the function defined by the minimum number of
steps taken on any instance of size n
● Average Case Complexity:
● the function defined by the average number of
steps taken on any instance of size n
 Motivation for Asymptotic
Analysis
● An exact computation of worst-case running
time can be difficult
● Function may have many terms:
📂 4n2 - 3n log n + 17.5 n - 43 n⅔ + 75
● An exact computation of worst-case running
time is unnecessary
● Remember that we are already approximating
running time by using RAM model
 Classifying functions by their
Asymptotic Growth Rates (1/2)
● asymptotic growth rate, asymptotic order, or
order of functions
● Comparing and classifying functions that ignores
📂 constant factors and
📂 small inputs.

● The Sets big oh O(g), big theta Θ(g), big

omega Ω(g)
 Classifying functions by their
Asymptotic Growth Rates (2/2)
● O(g(n)), Big-Oh of g of n, the Asymptotic
Upper Bound;
● Θ(g(n)), Theta of g of n, the Asymptotic Tight
Bound; and
● Ω(g(n)), Omega of g of n, the Asymptotic
Lower Bound.
Visualization of O(g(n))
●cg(n)

●f(n)

●n
0

56
 Big - O
Example: 1
Lets say f(n)=3n+2 and g(n)=n
We have to prove:
-f(n) ≤ cg(n)
- 3n+2 ≤c.n

Example: 1
So we can say:
for c=4 and for all n≥2
f(n) ≤ cg(n)
C n f(n)=3n+2 c.g(n)=c.n
4 1 5 4
4 2 8 8
4 3 11 12
4 5 17 20
 Examples
● 2n2 = O(n3):
2 3
2 2
● 2n≤ cn ⇒ 2 ≤ cn ⇒ c = 1 and
● n = O(n ): n = 2
0
●n2 ≤ cn2 ⇒ c ≥ 1 ⇒ c = 1
● 1000n2+1000n = O(n 2
and n0= 1):

●1000n2+1000n ≤ cn2 ≤ cn2+ 1000n ⇒ c=1001 and

n0 = 1
● n = O(n2):

●n ≤ cn2 ⇒ cn ≥ 1 ⇒ c = 1 and
58
n 0= 1
Big-O

59
 More Big-O
● Prove that:
● Let c = 21 and n0 = 4
● 21n2 > 20n2 + 2n + 5 for all n > 4
n2 > 2n + 5 for all n > 4
TRUE

60
 Big Omega – Notation
● Ω() – A lower bound

● n2 = Ω(n)
● Let c = 1, n0 = 2
● For all n ≥ 2, n2 > 1 × n

61
Visualization of Ω(g(n))
●f(n)

●cg(n)

●n
0

62
 Visualization of Ω(g(n))
Example: 1
Lets say f(n)=3n+2 and g(n)=n
We have to prove:
●f
( -f(n) ≥ cg(n)

n - 3n+2 ≥c.n
●c
)
g
( Example: 1
n So we can say:
●n )
for c=1 and for all n≥1
0
f(n) ≥ cg(n)
C n f(n)=3n+2 c.g(n)=c.n
1 1 5 1
1 2 8 2
1 3 11 3
1 4 14 4
 Visualization of Ω(g(n))

●f
(
n
●c
)
g
(
n
●n )
0
 Visualization of Ω(g(n))
Example: 2
Lets say f(n)=3n+2 and
●f g(n)=n2
( We have to prove:
n -f(n) ≥ cg(n)
●c
) - 3n+2 ≥c.n
g
(
n
●n ) We can not find such a constant
0
c so that for all n ≥1 can satisfy
our condition.
 Θ-notation

● Θ provides a tight bound

66
Visualization of Θ(g(n))
●c g(n)
2

●f(n)

●c g(n)
1

●n
0

67
 Visualization of Θ(g(n))
Example: Firstly c2 n f(n)=3n+2 c2.g(n)=c2.n
Lets say f(n)=3n+2 and g(n)=n 4 1 5 4
We have to prove: 4 2 8 8
-f(n) ≤ c g(n) 4 3 11 12
2
- 3n+2 ≤ c2.n 4 5 17 20

Example: Secondly c1 n f(n)=3n+2 c1.g(n)=c1.n

Lets say f(n)=3n+2 and 1 1 5 1
g(n)=n2 1 2 8 2
We have to prove: 1 3 11 3
-f(n) ≥ cg(n)
1 4 14 4
- 3n+2 ≥c.n

68
 Example 2
● Prove that:
● Let c = 21 and n0 = 10
● 21n3 > 20n3 + 7n + 1000 for all n > 10
n3 > 7n + 5 for all n > 10
TRUE, but we also need…
● Let c = 20 and n0 = 1
● 20n3 < 20n3 + 7n + 1000 for all n ≥ 1
TRUE

69
 O(1) constant
● Algorithms whose solutions are independent
of the size of the problem’s inputs are said to
have constant time complexity
● Constant time complexity is denoted as O(1)
 Some common rules

71
72
73
 Example
● Code:
● a = b;

● Complexity:

74
 Example
● Code:
● sum = 0;
● for (i=1; i <=n; i++)
● sum += n;

● Complexity:

75
 Example
● Code:
● sum = 0;
● for (j=1; j<=n; j++)
● for (i=1; i<=j; i++)
● sum++;
● for (k=0; k<n; k++)
● A[k] = k;
● Complexity:

76
 Example
● Code:
● sum1 = 0;
● for (i=1; i<=n; i++)
● for (j=1; j<=n; j++)
● sum1++;
● Complexity:

77
 Example
● Code:
● sum2 = 0;
● for (i=1; i<=n; i++)
● for (j=1; j<=i; j++)
● sum2++;
● Complexity:

78
 Example
● Code:
● sum1 = 0;
● for (k=1; k<=n; k*=2)
● for (j=1; j<=n; j++)
● sum1++;
● Complexity:

79
 Example
● Code:
● sum2 = 0;
● for (k=1; k<=n; k*=2)
● for (j=1; j<=k; j++)
● sum2++;
● Complexity:

80
Analysis of Insertion sort
Analysis of Insertion sort
 References
● Introduction to algorithm by Cormen, chapter 3
(Growth of functions)