CSE 105: Asymptotic
Analysis of Algorithms
Dr. Mohammed Eunus Ali
Professor
CSE, BUET
Some Slides from Tamassia & Goodrich
Running Time
• Most algorithms transform
input objects into output
objects.
• The running time of an
algorithm typically grows
with the input size.
• Average case time is often
difficult to determine.
• We focus on the worst case
running time.
• Easier to analyze
• Crucial to applications such as
games, finance and robotics
Experimental Studies
• Write a program
implementing the
algorithm
• Run the program with
inputs of varying size and
composition
• Use a method like
[Link]() to
get an accurate measure
of the actual running time
• Plot the results
Limitations of Experiments
• It is necessary to implement the algorithm,
which may be difficult
• Results may not be indicative of the
running time on other inputs not included
in the experiment.
• In order to compare two algorithms, the
same hardware and software environments
must be used
Theoretical Analysis
• Uses a high-level description of the
algorithm instead of an implementation
• Characterizes running time as a function
of the input size, n.
• Takes into account all possible inputs
• Allows us to evaluate the speed of an
algorithm independent of the
hardware/software environment
Pseudocode
• High-level description Example: find max
of an algorithm element of an array
• More structured than Algorithm arrayMax(A, n)
English prose Input array A of n integers
• Less detailed than a Output maximum element of
program A
• Preferred notation for
describing algorithms currentMax ← A[0]
• Hides program design for i ← 1 to n − 1 do
issues if A[i] > currentMax
then
currentMax ← A[i]
return currentMax
6
The Random Access Memory
(RAM) Model
• A CPU
• An potentially unbounded
bank of memory cells, 2
1
each of which can hold an 0
arbitrary number or
character
• Memory cells are numbered and accessing
any cell in memory takes unit time.
Primitive Operations
• Basic computations
• Examples:
performed by an algorithm
• Evaluating an
• Identifiable in pseudocode expression
• Largely independent from the • Assigning a value
to a variable
programming language
• Indexing into an
• Exact definition not important array
(we will see why later) • Calling a method
• Returning from a
• Assumed to take a constant
method
amount of time in the RAM
model
Counting Primitive
Operations
• By inspecting the pseudocode, we can determine the
maximum number of primitive operations executed by
an algorithm, as a function of the input size
Algorithm arrayMax (A, n) # operations
currentMax ← A[0] 2
for i ← 1 to n − 1 do 2n
if A[i] > currentMax then 2(n − 1)
currentMax ← A[i] 2(n − 1)
{ increment counter i } 2(n − 1)
return currentMax 1
Total 8n − 2
Estimating Running Time
• Algorithm arrayMax executes 8n − 2 primitive
operations in the worst case. Define:
a = Time taken by the fastest primitive operation
b = Time taken by the slowest primitive operation
• Let T(n) be worst-case time of arrayMax. Then
a (8n − 2) ≤ T(n) ≤ b(8n − 2)
• Hence, the running time T(n) is bounded by two
linear functions
Growth Rate of Running Time
• Changing the hardware/ software
environment
• Affects T(n) by a constant factor, but
• Does not alter the growth rate of T(n)
• The linear growth rate of the running
time T(n) is an intrinsic property of
algorithm arrayMax
11
Big Idea
Asymptotic (for large input size) Analysis
Algorithmic Analysis
Roadmap
1 2
RUNTIME COMPLEXITY
CODE Code FUNCTION Asymptotic CLASS
Modeling Analysis
for (i = 0; i < n;
i++) {
f(n) = 2n O(n)
a[i] = 1;
b[i] = 2;
}
● Algorithmic Analysis: The overall process of characterizing code
with a complexity class, consisting of:
○ Code Modeling: Code 🡪 Function describing code’s runtime
○ Asymptotic Analysis: Function 🡪 Complexity class describing
asymptotic behavior
Asymptotic Analysis
● First, we need to determine how long the algorithm takes,
in terms of the size of its input.
○ the running me of the algorithm as a function of the
size of its input.
● The second idea is that we must focus on how fast a
function grows with the input size.
○ We call this the rate of growth of the running me.
● By dropping the less significant terms and the constant
coefficients, we can focus on the important part of an
algorithm's running me—its rate of growth—without getting
mired in details that complicate our understanding.
○ When we drop the constant coefficients and the less
significant terms,
Examples
● f(n) = 6n^2 + 100n + 300
● Removing Lower order terms and constants
Asymptotic Notations: Big Oh, and
Omega, and Theta
Big-Oh
● Big-Oh is an upper bound
○ My code takes at most
this long to run
● Big-Omega is a lower bound
○ My code takes at least this Big-Omega
long to run
● Big Theta is “equal to (tight
bound)”
○ My code takes “exactly”* this
long to run Big-Theta
○ *Except for constant factors and
lower order terms
○ Only exists when Big-Oh ==
Big-Omega!
Examples
Seven Important Functions
• Seven functions that
often appear in
algorithm analysis:
• Constant ≈ 1
• Logarithmic ≈ log n
• Linear ≈ n
• N-Log-N ≈ n log n
• Quadratic ≈ n2
• Cubic ≈ n3
• Exponential ≈ 2n
• In a log-log chart, the
slope of the line
corresponds to the
growth rate of the
function
Constant Factors
• The growth rate is
not affected by
• constant factors or
• lower-order terms
• Examples
• 102n + 105 is a linear
function
• 105n2 + 108n is a
quadratic function
19
Case Study: Linear Search
● Let’s analyze this realistic piece of
code! toFi 2
nd
int linearSearch(int[] arr, int a 2 3 9 4 5
toFind) { rr
for (int i = 0; i < i
[Link]; i++) {
if (arr[i] == toFind) {
return i;
} toFi 8
} nd
return -1; a 2 3 9 4 5
•}What’s the first step? rr
- We have code, so we need to convert to i
a function describing its runtime
- Then we know we can use asymptotic
analysis to get bounds
*Remember, these
Let’s Model This Code! constants don’t really
matter (we’ll start
int linearSearch(int[] arr, int phasing them out
soon)
toFind) {
for (int i = 0; i <
[Link]; i++) { +2
if (arr[i] == toFind) +1
{
return i; +1 +3 *
} ?
Same problem as
} before:
return -1;+1 How many times does
} loop run?
When would that
happen?
● Suppose the loop runs n times? toFind not
○ f(n) = 3n + 1 present These are
● Suppose the loop only runs toFind at key!
once?
○ f(n) = 2 beginning
Best Case
Worst
Case
toFind 2
toFind 8
arr 2 3 9 4 5 arr 2 3 9 4 5
i
i
f(n) = 2 f(n) = 3n + 1
After asymptotic analysis: After asymptotic analysis:
O(1) Θ(1) O(n) Θ(n)
Prime Checking
boolean isPrime(int n) {
int toTest = 2; +1
while(toTest < n) { +1
if (n % toTest == 0) { +2
return false; +1
~+5 *?
} else {
toTest += 1; +2
}
}
return true; +1
}
Prime Checking Runtime
Is the runtime
O(1) or O(n)?
More than half
the time we
need 3 or fewer
iterations. Is it
O(1)?
But we can
always come up
with another
value of n to
make it take n
iterations. So
This is why we have definitions!
O(n)?
Our Upgraded Tool:
Asymptotic Analysis
TIGHT
2 BIG-OH O(n2)
RUNTIME Asympt
FUNCTION otic
BIG-THETA Θ(n2)
Analysis
f(n) = 10n2 + TIGHT
13n + 2 BIG-OMEG
A
We’ve upgraded our Asymptotic Analysis tool to convey more useful information!
Having 3 different types of bounds means we can still characterize the function in simple
terms, but describe it more thoroughly than just Big-Oh.
Algorithmic Analysis
Roadmap
TIGHT
2 BIG-OH
O(n)
1
RUNTIME Asympt
CODE Code FUNCTION BIG-THETA
otic
Modeling
Analysis Θ(n)
for (i = 0; i < n;
i++) {
f(n) =
TIGHT
a[i] = 1; 2n BIG-OMEG
b[i] = 2;
} A
Now, let’s look at this tool We just finished building this
in more depth. How tool to characterize a function
exactly are we coming up in terms of some useful
with that function? bounds!
Summarizing Big Theta, Oh, Omega