Lecture No. 04
Time Complexity of Algorithms
(Asymptotic Notations)
•Complexity Analysis
•Growth of Functions
•Asymptotic Notations
•Usefulness of Notations
•Reflexivity, Symmetry, Transitivity Relations over
, , O, and o
•Relation between , and O
•Various Examples Explaining each concept
Today Covered
•The level in difficulty in solving mathematically
posed problems as measured by
–The time
(time complexity)
–number of steps or arithmetic operations
(computational complexity)
–memory space required
–(space complexity)
What is Complexity?
Algorithm Growth Rates
•It measures algorithm efficiency
What means by efficient?
▪If running time is bounded by polynomial in the input
Notations for Asymptotic performance
•How running time increases with input size
•O, Omega, Theta, etc. for asymptotic running time
•These notations defined in terms of functions whose
domains are natural numbers
•convenient for worst case running time
•Algorithms, asymptotically efficient best choice
Algorithms Growth Rate
•Algorithm analysis means predicting resources such as
–computational time
–memory
–computer hardware etc
•Worst case analysis
–Provides an upper bound on running time
–An absolute guarantee
•Average case analysis
–Provides the expected running time
– Very useful, but treat with care: what is “average”?
•Random (equally likely) inputs
•Real-life inputs
Complexity Analysis
Let us suppose that
•Dn= set of inputs of size n for the problem
•I = an element of Dn.
•t(I) = number of basic operations performed on I
•Define a function W by
W(n) = max{t(I) | I Dn}
called the worst-case complexity of the algorithm
•W(n) is the maximum number of basic operations
performed by the algorithm on any input of size n.
•Please note that the input, I, for which an algorithm
behaves worst depends on the particular algorithm.
Worst-case Analysis
Asymptotic Notations Properties
•Categorize algorithms based on asymptotic growth
rate e.g. linear, quadratic, polynomial, exponential
•Ignore small constant and small inputs
•Estimate upper bound and lower bound on growth
