Module 1
Introduction
Asymptotic Notations and Basic
Efficiency Classes
O Notation :
Notation :
Notationθ:
Using Limits for comparing order of
growth :
Useful Property involving
Asymptotic Notations :
THEOREM
If t1(n) ∈ O(g1(n)) and t2(n) ∈ O(g2(n)), then
t1(n) + t2(n) ∈ O(max{g1(n), g2(n)})
PROOF
The proof extends to orders of growth the following simple fact about four
arbitrary real numbers a1, b1, a2, b2:
X Y X AND Y
if a1 ≤ b1 and a2 ≤ b2, then a1 + a2 ≤ 2 max{b1, b2}. F F F
F T F
T F F
Ex: a1=5 a2 =2, b1 = 3 b2=4 T T T
a1=3 a2 =5, b1 = 7 b2=12
Mathematical Analysis of Non-Recursive Algorithms
1) problem of finding the value of the largest element in a list of n numbers
Basic operation
2) Element uniqueness problem: check whether all the elements in a given array
of n elements are distinct.
3) Given two n × n matrices A and B, compute their product C = AB
4) finds the number of binary digits in the binary representation of a positive
decimal integer
General Plan for Analyzing the Time Efficiency of Non-recursive 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 the
innermost loop.)
3. Check whether the number of times the basic operation is executed
depends only on the size of an input. If it also depends on some additional
property, the worst-case, average-case, and, if necessary, best-case
efficiencies have to be investigated separately.
4. Set up a sum expressing the number of times the algorithm’s basic
operation is executed.
5. Using standard formulas and rules of sum manipulation, either find a closed
form formula for the count or, at the very least, establish its order of growth
Mathematical Analysis of Recursive
Algorithms
1) Compute the factorial function F (n) = n!
we need an initial condition that tells us the value with which the
sequence starts
Such equations are called recurrence relations or recurrences
• solving recurrence relations can be done by a method of backward
substitutions.
• The method’s idea (and the reason for the name) is immediately clear from the
way it applies to solving our particular recurrence
2) Tower of Hanoi puzzle.
3) finds the number of binary digits in the binary representation of a positive
decimal integer
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
vary on different inputs of the same size; if it can, the worst-case, average-
case, and best-case efficiencies must be investigated separately.
4. Set up a recurrence relation, with an appropriate initial condition, for the
number of times the basic operation is executed.
5. Solve the recurrence or, at least, ascertain the order of growth of its solution
Chapter 3
Brute Force
Introduction
• Brute force is a straightforward approach to solving a problem
• Directly based on the problem statement and definitions of the concepts
involved
• “Just do it!” would be another way to describe the prescription of the brute-
force approach
• Ex: compute a^n
a^n = a ∗ ... ∗ a
n times
• 2 Algorithms :
1) Selection Sort
2) Sequential Search
Selection Sort :
Require n-1 passes
Pseudocode :
for (i=0 ; i<n-1 ; i++) If(min !=i)
{ {
min=j; swap(a[i],a[min])
for (j=i+1; j<n; j++) }
{ }
if(a[j] < a[min])
{
min=j;
}
}
Thus, selection sort is O(n2) algorithm on all inputs.
Sequential Search
