Module1

INTRODUCTION AND ALGORITHM

ANALYSIS

Algorithm Analysis, Mathematical Background, Model,

What to Analyze, Running Time Calculations, General
Rules.
Algorithm
Algorithms are step - by - step instructions that • Boil some water in a Pan
help us in doing some tasks. • Add maggie into it
In computer science terminologies, • Add maggie masala
an algorithm is defined as a set of well-defined • Check for toppings
instructions that helps us to solve any particular
problem. • If present :
• Sprinkle them
• Else :
Example: An algorithm for cooking Maggie => • Do not sprinkle
• Serve the maggie
A well defined computational procedure that takes set of values as
input and transform it into an output.
Writing an algorithm
Why analysis of algorithm
• There are many ways to go from city "A" to city “B": by night, by
bus, by train and also by bicycle. Depending on availability and
convenience, we choose the one that suits us best.

• Multiple algorithms are available for solving the same problem (for
example, a sorting problem has many algorithms, like insertion
sort, selection sort, quick sort and many more).

• Algorithm analysis helps us to determine which algorithm is most

efficient in terms of time and space consumed.
Analysis of Algorithm • The goal is to compare different
algorithms that are used to solve
• The process of finding the the same problem.
computational complexity of any
algorithm. • This is done to evaluate which
method solves a certain problem
• Computational complexity refers to more quickly, efficiently, and
the amount of time taken, space, memory-wise.
and any other resources needed to
execute(run) the algorithm.
• We get an idea of how the
algorithm will scale with the
• How fast or slow does a particular
variation (change) in the input
algorithm or piece of code
size.
perform?

• Better complexity, better solution.

Analyzing the Algorithm

Time Space

• How much time does an • How much space an algorithm

Algorithm take in order to will consume to produce the
desired output?
produce a desired output?
• The amount of memory it utilizes.
• The number of operations it
runs to find the solution.

• How fast the algorithm runs

as the size of input increases.
Analyzing the Algorithm

• Step by step instructions

• Finite sets of steps to solve a
problem
• It provides correct result for
every input instances.
• Efficiency in the algorithm is very
important.
Measuring Performance
Summary of the Notations

Notation Definition Representation Focuses on

Big-O(O) Upper Bound (Worst-case) The maximum time/space complexity Worst-case scenario

Omega(Ω) Lower Bound (Best-case) The minimum time/space complexity Best-case scenario

Theta(θ) Tight Bound (Exact bound) The exact time/space complexity Average behavior (tight bound)
Why analyzing the time complexity is so important?
Asymptotic Notations

These are important types of analysis of algorithms.

Best case
Average case
Worst case
Asymptotic Notation
• Tell us about how good an algorithm performs when compared to
another algorithm.
• Analyzes two algorithms based on their performance when the input
size is varied (increased or decreased).
• To identify the upper and lower bounds. To represent these upper
and lower bounds, we need some kind of syntax, and that is the
subject of the following discussion.

• Big-Oh (𝑂) notation.

• There are three types of Asymptotic Notations:

• Big Omega (Ω) notation.

• Big Theta (Θ) notation.
Worst case: Defines the input for which the algorithm takes a
long time. Input is the one for which the algorithm runs the
slowest

Best case:Defines the input for which the algorithm takes the
least time. Input is the one for which the algorithm runs the
fastest.
best
case
We want to search
for num = 4

4 5 1 7 2 9 3 8
best
case
We want to search
for num = 4

4 5 1 7 2 9 3 8
worst case

We want to search
for num = 6

4 5 1 7 2 9 3 8
worst case

We want to search
for num = 6

4 5 1 7 2 9 3 8
• The best case time or space
complexity is often represented in
terms of the BigOmega (Ω) notation
Best case analysis of Algorithm • Searching an element in the array:
• Provides the lower bound on the algorithm's
running time for any given input. int linear_search(int arr, int l, int target) {
• Any program will need at least (greater than or
equal to) that time to run.
int i;
for (i = 0; i < l; i++) {
the best case time complexity is Ω(𝑁), then we can
Example: Suppose we have an algorithm that has if (arr[i] == target) {
return arr[i]
Ω(𝑁)time to run, it can never take sometime less
say that the program will take a minimum of

than that. }
}
return -1
}
The number you are searching for is
present at the very beginning index of
the array. In that case, your algorithm
will take Ω(1) or constant time to find
the number in the best case.
• The worst-case time or space complexity is
often represented in terms of the Big
Oh (O) notation.
Worst case analysis
• Provides the upper bound on the running
time of the algorithm for any given input. • Example: Searching an element at the end of
• It states that any program will need a maximum the array.
of time (less than or equal to) to run.

complexity is 𝑂(𝑁2), then we can say that the

Example: An algorithm that has the worst-case time • In this case, we will have to traverse the
program will take a maximum of 𝑂(𝑁2)time to
whole array before finding the element.
run, for an input of size 𝑁 it can never take

• Worst case for this algorithm is 𝑂(𝑁)itself.

more time than that to run.

• We have to go through at most 𝑁 elements

before finding our target.
Order of Magnitude
Average Case
• For a given algorithm, we can represent the best. worst and
average cases in the form of expressions.
• Let f(n) be the function which represents the given algorithm.
• f (n) = n2 + 500, for worst case
• f (n) = n + 100n + 500, for best case
• Similarly for the average case. The expression defines the inputs
with which the algorithm takes the average running time (or
memory)
4 5 1 7 2 6 3 8
4 5 1 7 2 6 3 8
def arr_min(arr):
min =
float('inf')
for elem in arr:
if elem < min:
min = elem
return min
def arr_min(arr):
min =
float('inf')
for elem in arr:
if elem < min:
min = elem
return min
def arr_min(arr):
min =
float('inf')
for elem in arr:
if elem < min:
min = elem
return min
def arr_min(arr):
min =
float('inf')
for elem in arr:
if elem < min:
min = elem
return min
def arr_min(arr):
min =
float('inf')
for elem in arr:
if elem < min:
min = elem
return min
def arr_min(arr):
min =
float('inf')
for elem in arr:
if elem < min:
min = elem
return min
def arr_min(arr):
min =
float('inf')
for elem in arr:
if elem < min:
min = elem
return min
def
int_sum(n):
sum = 0
while n >
0:
sum += n
n -= 1
return sum
def int_sum(n):
return
n(n+1)/2
Ways of solving recurrences

• Substitution Method (If we know the answer)

• Recursion Tree Method (Very useful !)
• Master Theorem (Save our effort)
Substitution Method
(if we know the
answer)
HowT(n)
to solve this?
= 2T(bn/2c) with T(1) =
+ n, 1
1. Make a guess (say, T(n) = O(f(n)) ),
and
2. Show it by induction
• For example, to show upper bound, we
find constants c and n0 such that
T(n) · c f(n)
52
for n = n , n +1, n +2, …
Substitution Method
(if we know the
answer)
HowT(n)
to solve this?
= 2T(bn/2c) with T(1) =
+ n, 1
1. Make a guess (T(n) = O(n log n)), and
2. Show it by induction
• Find c = 2, and n0 = 2
• Base Case: By the recurrence, T(2) =
3, T(3)
= 5. Both cases satisfy T(n) · cn log n
• Induction Case ? 53
Substitution Method
(if we know the answer)
• Induction Case:
Assume the guess is true for all n =
2,3,…,k For n = k+1, we have:
T(n) = 2T(bn/2c) + n

· 2cbn/2c log
bn/2c+ n Induction
case is true

· cn log (n/2) + n
= cn log n – cn + n ·
cn log n
54
Substitution Method
(if we know the answer)
Q. How did we know the value of c and
n0 ?
A. If induction works, the induction
case must be correct 🡺 c ¸ 1
Then, we find that by setting c = 2,
our guess is correct as soon as n0 =
2
Alternatively, we can also use c
= 1.3 Then, we just need a larger
55
n =4
Substitution Method
(New Challenge 1)
How to solve this?

T(n) = 2T( n )+
log n ?

Hint: Change variable: Set m

= log n

56
Substitution Method
(New Challenge 1)
Set m = log n , we get
T(2m) = 2T(2m/2) +
m

Next, set S(m) = T(2m)

S(m) = 2S(m/2) +
m
We solve S(m) = O(m log m)
🡺 T(n) = O(log n log log n) 57
Recursion Tree Method
( Nothing Special… Very Useful ! )

How to solve this?

T(n) = 2T(n/2) + with T(1) =
n 2, 1

58
Recursion Tree Method
( Nothing Special… Very Useful ! )
Expanding the terms, we get:
T(n) = n2 + 2T(n/2)
= n2 + 2n2/4 + 4T(n/4)
= n + 2n2/4 + 4n2/16 +
8T(n/8)
=…

Σ
= k=0 to log n– 1 (1/2)k n2 + 2log n
T(1)
59
2 2 2
Recursion Tree Method
( Recursion Tree View )

We can express the previous recurrence

by:

60
Further expressing gives us:

This term is
from T(n/2)
61
Recursion Tree Method
( New Challenge )

How to solve
this? with T(1) =
T(n) = T(n/3) + T(2n/3) + 1
What will be then,
recursion tree
view?

62
The corresponding recursion tree view is:

63
Master Method
( Save our effort )

When the recurrence is in a special form,

we can apply the Master Theorem to
solve the recurrence immediately

The Master Theorem has 3 cases …

64
Master Theorem
Let T(n) = aT(n/b) +
with a f(n)
≥ 1 and b > 1 are constants.

Theorem: (Case 1: Very Small f(n) )

If f(n) = O(nlogb a - ε) for some constant
ε>0
the T(n) = Θ(nlogb
n a
)

65
Theorem: (Case 2: Moderate f(n) )
If f(n) = Θ(nlogb a),
the T(n) = Θ(nlogb a log
n n)
Theorem: (Case 3: Very large f(n) )
If (i) f(n) = Ω(nlogb a + ε) for some constant
ε>0
and (ii) a f(n/b) ≤ c f(n) for some constant c
< 1,
the T(n) = all sufficiently large n
n Θ(f(n))
66
Master Theorem (Exercises)
1. Solve T(n) = 9T(n/3) + n

2. Solve T(n) = 9T(n/3) + n2

3. Solve T(n) = 9T(n/3) + n3

4. How about this?

T(n) = 9T(n/3) + n log
n ?
67