Introduction
• Performance analysis
• Space and time complexity
• Growth of function : Big- Oh,Omega Theta notation
• Mathematical background for algorithm analysis.
• Complexity class: Definition of P, NP, NP-Hard, NP-Complete
• Analysis of selection sort, insertion sort.
• Recurrences: The substitution method, Recursion tree method,
Master method
Introduction
Performance analysis
• The efficiency of an algorithm can be decided by measuring the
performance of an algorithm by computing two factors.
1. Amount of time taken by an algorithm to execute
2. Amount of storage required by an algorithm
This is known as time complexity and space complexity of an algorithm
Algorithmic Notations
[Link]/procedure Name
[Link]
variable name := Expression
variable name Expression
[Link]
x<-->y
[Link] statement
Read
5. Output Statement
write
Algorithmic Notations
[Link] statement
[Link] – while
[Link] construct
[Link]
10. Case construct
[Link]
[Link][A]
13.A[i..j]
[Link] operators
[Link] results
[Link] statement
[Link]/subprocedure/function
Expressing Algorithmic
[Link]
[Link] code
[Link] Programming Language
Algorithm
[Link] Algorithm
[Link] Algorithm
Algorithm Efficiency
• The algorithm’s efficiency as a function of the number of
elements to be processed.
• f(n)=efficiency
• Loops
Linear loops
Logarithmic loops
Nested loops
Algorithm Efficiency
1. Sequence of statements
statement 1
statement 2
statement 3
statement 4
statement 5
Algorithm Efficiency
1. If then else statement
if(condition)
{
sequence of statement(s)
}
else
{
sequence of statement(s)
}
What will be the worst case time?
Algorithm Efficiency
1. for loop
for(i=0;i<n;i++)
{
Sequence of statements
}
What will be the frequence count?
Loop executed: n times
Statement(s) : n times
Assume , statements are simple : O(1)
Total time for the ‘for’ loop is N*O(1)= O(n)
Linear loops
1. i=1
2. Loop(i<=1000)
1. Application code
2. i= i+1
f(n) = n 1. i=1
2. Loop(i<=1000)
1. Application code
2. i= i+1
Logarithmic loops
1. i=1 1. i=1000
2. Loop(i<=1000) 2. Loop(i>=1)
1. Application code 1. Application code
2. i= i*2 2. i= i/2
Multiply Divide
F(n) = log(n)
Nested Loops
Nested
loops
Linear Dependent
Quadratic
Logarithmic Quadratic
Linear logarithmic
1. i=1
2. Loop(i<=10)
1. j=1
2. Loop(j<=10)
[Link] code
2.j=j*2
3.i=i+1
Inner loop …?
Outer loop…?
No, of Iterations….?
F(n)=….?
Dependent Quadratic
1. i=1
2. Loop(i<=10)
1. j=1
2. Loop(j<=i)
[Link] code
2.j=j+1
[Link] times inner loop gets
3.i=i+1 executes …?
Outer loop…?
No, of Iterations….?
F(n)=….?
Quadratic
1. i=1
2. Loop(i<=10)
1. j=1
2. Loop(j<=10)
[Link] code
2.j=j+1
[Link] times inner loop gets
3.i=i+1 executes …?
Outer loop…?
No, of Iterations….?
F(n)=….?
Example
1. N
2. Sum=0
3. i=0
4. While i < N
5. Number = read number from user
6. Sum=Sum+number
7. i=i+1
8. Mean=Sum/N
Complexity of above code…..?
Space Complexity
• Space Complexity of an algorithm is the amount of memory it
needs to run the completion.
• Memory space S(P) needed by a Program P consist of two
components:
1. A fixed part
2. A variable part
Space Complexity
• A fixed part
(needed for Instruction space (byte code) ,Simple variable
space, constant space etc. represented by C)
• A variable part
(dependent on a particular instance of input and output data ,
represented by Sp(instance))
• S(P)= C + Sp(instance)
Examples
Example1:
[Link] abc( a,b,c)
2.{
3. Return a+b+bxc(a+b+c)/(a+b)+4.0
4. }
Here for every instance 3 computer words required to store variable a,b and c
Sp()=3 , S(P)=3
Examples
Example2:
[Link] Sum( a[],n))
2.{
3. S :=0
4. For i=1 to n do
5. S:= S + a[i]
6. return S
7. }
Here for every instance need to store array a[] and n
space needed to store n = 1 word
space needed to store a[] = n words
space needed to store i and s = 2 words
Sp(n)=(n+3)
Hence S(P)=(n+3)
Asymptotic Notations
Big-oh Notation
• Big-oh is the formal method of expressing the upper bound of an
algorithm’s running time.
• It is a measure of the longest amount of time it could possibly take for the
algorithm to complete.
• Definition: Let f(n) anf g(n) be two non negative functions . Let n0 and
constant C are two integers such that n0 denotes some value of input and
n>[Link] C is some constant such that C>0
• f(n)<=C*g(n) , then f(n) is big-oh of g(n) .It is also denoted as f(n)E g(n)
• f(n) is less than g(n) if g(n) is multiple of some constant C
Asymptotic Notations
Big-oh Notation
Asymptotic Notations
Example
F(n)=2n+2 and g(n)=n2
Then we have to find some constant C , so that f(n)<=C*g(n)
If n=1 , f(n)=2n+2 = 2+2=4
g(n)= n2 = 1
i.e. g(n) > f(n)
Asymptotic Notations
If n=1 , f(n)=2n+2 = 2+2=4
g(n)= n2 = 1
i.e. f(n) > g(n)
If n=2 , f(n)=2n+2 = 4+2=6
g(n)= n2 = 4
again f(n) > g(n)
Asymptotic Notations
If n=3 , f(n)=2n+2 = 6+2=8
g(n)= n2 = 9
Here f(n) <g(n) is true
Hence we conclude that for n>2 ,we obtain f(n)<g(n)
Asymptotic Notations
Omega Notation
• It is denoted by Ω
• This notation is used to represent the lower bound of algorithm’s
running time.
• Using this notation we can denote shortest amount of time taken by
algorithm
• Definition: A function f(n) is said to be in Ω (g(n)) if f(n) is bounded
below by some positive constant multiple of g(n) such that
f(n)>=C*g(n) for all n>=n0
• It is denoted as f(n)E Ω(g(n))
Asymptotic Notations
Omega Notation
Asymptotic Notations
Example
F(n)=2n2 +5 and g(n)=7n
If n=0 , f(n)=5 g(n)=7 f(n) > g(n)
If n=1 , f(n)=7 g(n)=7 f(n) = g(n)
If n=2 , f(n)=13 g(n)=14 f(n) =<g(n)
If n=3 , f(n)=23 g(n)=21 f(n) >g(n)
Thus for n>=3 , we get f(n) > C*g(n)
Asymptotic Notations
Theta Notation
• It is denoted by Θ
• By this method running time is between upper bound and
lower bound
• Definition: Let f(n) and g(n) be two non negative functions.
There are two positive constants namely C1 and C2 such that
C1*g(n)<=f(n)<=C2*g(n) for all n>=n0
Asymptotic Notations
Theta Notation
Asymptotic Notations
Example
F(n)=3n+2 and g(n)=n
C1*g(n)<=f(n)<=C2*g(n)
C2=4
C1=1
Insertion Sort
▪ Insertion sort is a Simple sorting algorithm , a comparison sort , in which the sorted
array(list) is built using one entry at a time.
▪ It is much less efficient on larger list than some more advanced algorithms such as Quick
Sort , Merge Sort and Heap Sort but it has various advantages
1. Simple to implement
2. Efficient on small data sets
3. Efficient on data sets which are already substantially sorted
4. More efficient in practice than most other simple O(n2) algorithms , such as selection
sort or bubble sort. The Average time is n2/4 and it is linear in best case
5. Stable(Does not change relative order of elements with equal keys
6. In-Place( Only requires a constant amount O(1) of extra memory space
7. It is an Online algorithm , in that it can sort the list as it receives it
Insertion Sort (Pseudocode)
Algorithm InsertionSort(A,n)
// Sort the array into increasing order ;n>=1
For j:=2 to n do
{
item=a[j] ; i=j-1
while((i>=1) and(item<a[i])) do
{
a[i+1]:=a[i]
i=i-1
}
a[i+1]:=item
}
InsertionSort(Analysis)
• When an array of elements is almost sorted then it is best case
complexity
• The best case complexity of insertion sort is O(n)
• If an array is randomly distributed then it results in average
case time complexity which is O(n2)
• If the list of elements is arranged in descending order and if we
want to sort an elements in ascending order then it results in
worst case time complexity which is O(n2)
Selection Sort(Simple algorithm)
1. For i:= 1 to n do
2. {
3. Examine a[i] to a[n] and
4. Suppose the smallest element is at a[j]
5. Interchange a[i] with a[j]
6. }
Selection Sort(pseudocode)
Algorithm SelectionSort(A,n)
// Sort the array into increasing order ;n>=1
{
for i := 1 to n do
{
j:=i
for k:= i+1 to n do
if(a[k] < a[j] then j:=k
temp:=a[i] ; a[i]:=a[j] ; a[j]=temp
}
}
Selection Sort(Analysis)
• In this algorithm , for selection the smallest element from the
array(list) requires scanning all n elements. This requires n – 1
comparisons and then swapping it into first position .
• Finding the next smallest elements requires scanning the remaining
n-1 elements and so on.
• Thus the algorithm requires
(n-1)+(n-2)+(n-3)……..+2+1=n(n-1)/2
comparisons
• So the time complexity is O(n2)
Recurrences
• The recurrence equation is an equation that defines a sequence
recursively.
• It is normally in following form:
T(n) = T(n-1) + n for n>0 …..(I)
T(0)=0 ….(II)
• Here eq.(I) is called recurrence relation and equation (II) is called
initial condition
• The recurrence equation can have infinite number of sequences
• The general solution to the recursive function specifies some
formula.
Recurrences
• For example: consider a recurrence relation
f(n)=2f(n-1) + 1 for n>1
f(1)= 1
• Then by solving this recurrence relation we get f(n)= 2n − 1
When n = 1,2,3 and 4
Solving Recurrence Equations
• Substitution Method
• Tree method
• Master Method
Solving Recurrence Equations
Substitution Method
• In the substitution method for solving recurrences we
1. Guess the form of the solution.
2. Use mathematical induction to find the constants and
show
that the solution works.
• There are two types of substitution
a. Forward Substitution
b. Backward Substitution
Solving Recurrence Equations
Forward Substitution Method
• This method makes use of an initial condition in the initial term
and value for the next term is generated. This process is continued
until some formula is guessed
• Thus in this kind of substitution method , we use recurrence
equations to generate the few terms
• Example
consider the recurrence relation
T(n)=T(n-1) + n
With initial condition T(0)=0
Solving Recurrence Equations
Forward Substitution Method
Let
T(n)=T(n-1) + n
If n=1 then T(1)= T(0)+1
=0+1
T(1 ) = 1 …..(1)
If n=2 then T(2)= T(1)+2
=1+2
T(2 ) = 3 …..(2)
Solving Recurrence Equations
Forward Substitution Method
If n=3 then T(3)= T(2)+3
=3+3
T(3 ) = 6 …..(3)
By observing above generated equations , we can derive a formula
T(n)=n(n+1)/2 = n2/2 + n/2
• We can also denote T(n) in termsof big 0h notation
T(n) = O(n2)
But in practice , it is difficult to guess the pattern from forward
subtition .Hence this method is not very often used.
Backward Substitution
• In this method backward values are substituted recursively in order to derive some
formula
• For example T(n)=T(n-1) + n …..(1)
with initial condition T(0)=0
T(n-1) = T(n-1-1)+(n-1) ….(2)
Putting eq.(2) in eq.(1)
T(n)=T(n-2)+(n-1)+n …(3)
Let T(n-2)= T(n-2-1)+(n-2) …..(4)
Putting eq(4) in eq.(3) , we get
T(n) = T(n-3)+(n-2)+(n-1)+n
..
= T(n-k)+(n-k+1)+(n-k+2)+….+n
If k=n
T(n)=T(0)+1+2+…..n
= 0+1+2….+n
= n(N+1)/2=n2/2 + n/2
Examples
Tree method
Master method
• Master method is used for determining asymptotic solution to
recurrence of a specific form
T(n) = aT(n/b) + f(n) a>=1 , b>1
– Where a= The number of sub-problem in the recursion
– 1/b = The portion of the original problem represented by each
sub-problem
– f(n) = cost of dividing the problem + cost of merging the solution
Master method
• Master method is used for determining asymptotic solution to
recurrence of a specific form
T(n) = aT(n/b) + f(n) a>=1 , b>1
– Where a= The number of sub-problem in the recursion
– 1/b = The portion of the original problem represented by each
sub-problem
– f(n) = cost of dividing the problem + cost of merging the solution
Three cases of master method
Three cases of master method
Examples
Examples
Examples
Examples
Master method :Examples
1. T(n) = 8T(n/2) + 1000n2
2. T(n) = 9T(n/3) + n3
3. T(n) = 9T(n/3) + n2
Master method :Examples
1. T(n) = 8T(n/2) + 1000n2
Solution : The general form of master theorem is
T(n) = aT(n/b) + f(n) a>=1 , b>1
The variables get the following values
a=8 , b=2 , f(n)= 1000n2
Logba = 3
now we have to check the following condition hold
Master method :Examples
f(n) = O(n3 -1) // if we choose E=1
1000n2 = f(n2 )
Since this equation holds
First case of master theorem applies to the given recurrence
relation, thus resulting the conclusion
T(n) = O(n3 )
Master method :Examples
T(n) = 9T(n/3) + n3
Master method :Examples
Master method :Examples