Algorithms & Data Structures

CS211

Complexity
Analysis

Lectures 2 & 3

Samar Alsaleh
Spring 2022
 04

03 Finishing Thoughts
Summary & resources

02 Code Complexity
Finding complexity of code structures

Today’s 01 Asymptotic Complexity

Asymptotic notations, rules and comparisons

Agenda Intro to Algorithm Analysis

Concept of running time and growth functions
Today’s 01

Agenda Intro to Algorithm Analysis

Concept of running time and growth functions
Behind the Scenes

Client: wants to solve

problem efficiently

Programmer: needs to Student (you!): might play

develop a working solution all of these roles someday

Theoretician: seeks to
understand

4
Running Time

How many times do you

have to turn the crank?

Working model of Babbage’s Analytical Engine

5
 Measuring the Running Time
- One opKon is to perform experimental studies
- Write a program implemenKng the algorithm
- Run the program with inputs of varying size
- Use a method like [Link]() to get
an accurate measure of the actual running Kme
- Compare/Plot the results
- LimitaKons of experiments
- It is necessary to implement the algorithm, which may be
difficult
- Results may not be indicaKve of the running Kme on other
inputs not included in the experiment
- In order to compare two algorithms, the same hardware and
soSware environments must be used
6
 Measuring the Running Time (cont.)
- A beTer opKon is to use mathemaKcal models
- Uses a high-level descripKon of the algorithm
instead of an implementaKon
- Characterizes running Kme as a funcKon of the
input size, n
- Takes into account all possible inputs
- Allows us to evaluate the speed of an algorithm
independent of the hardware/soSware environment

7
 Algorithm Analysis
Why analyze algorithms?
- The same problem can be solved with different algorithms which differ in efficiency
- We analyze the algorithms to:
- Evaluate algorithm performance
- Compare different algorithms
- Provide guarantees
- Understand theoreKcal basis
- We focus on analyzing :
- Running Kme
- Memory usage
- Worst-case and typical case
➔ Analysis of algorithms compares algorithms NOT programs
8
 Algorithm Analysis (cont.)
- The analysis of algorithms involves evaluaKng an algorithm in terms of Kme or space
efficiency
- An algorithm that solves a problem but requires a year is hardly of any use
- Likewise, an algorithm that requires thousands of gigabytes of main memory is not
(currently) useful on most machines
- The efficiency of an algorithm is usually expressed in terms of CPU Kme
- To evaluate an algorithm’s efficiency, real-Kme units such as microseconds and
nanoseconds should not be used
- Rather, logical units that express a relaKonship between the input size n (of a file or
an array) and the amount of Kme t required to process the data should be used

9
 Algorithm Analysis (cont.)

- An everyday example: washing dishes

- Suppose washing a dish takes 30 seconds and drying a dish takes an addiKonal 30 seconds
- Then it would take n minutes to wash and dry n dishes
- This computaKon can be expressed as:
time(n dishes) = n × (30 sec wash time + 30 sec dry time)
= n × (60 sec) = n × (1 minute)
= n minutes 10
 Problem/Input Size
- If each line takes constant Kme the whole algorithm will take constant Kme, right?
Wrong!
- The number of steps performed of an algorithm varies based on the size of instance,
called problem or input size
- For every algorithm we want to analyze, we need to define the size of the problem
- Some examples:
- The dishwashing problem has a size n – number of dishes to be washed/dried
- For a search algorithm, the size of the problem is the size of the search pool
- For a sorKng algorithm, the size of the program is the number of elements to be sorted
- The efficiency of an algorithm is always stated as a funcKon of the problem size
- We generally use the variable n to represent the problem size
- Typically, the size of the input (n) is the main consideraKon
11
 Problem Size MaVers!
- Some example algorithms and their expected running Kmes based on the input size:

A brute force Traveling

Problem Size Linear Merge Bubble An algorithm with
search salesman
(n ) search sort sort 3 nested loops
algorithm problem

12
 Machine Independence
- The evaluaKon of efficiency should be machine independent
- It is not useful to measure how fast the algorithm runs as this depends on which
computer, OS, programming language, compiler, and kind of inputs are used in tesKng
- Instead,
- we count the number of basic operaKons the algorithm performs
- A basic operaKon is an operaKon which takes a constant amount of Kme to execute
- we calculate how this number depends on the size of the input
- The efficiency of an algorithm is the number of basic operaKons it performs
- This number is a funcKon of the input size n

13
 Basic OperaKons
Common Basic Operations
Operation Example
Arithmetic operations * , /, % , + , ×
Assignment statements of simple data types x = 12
Reading of primitive types [Link]
Writing of a primitive type [Link]
Simple conditional tests if(x < 3) …
Method call addXY(x, y);
A method's return statement return x;
Memory Access fetch/store
Notes:
- Assignment and increment/decrement operaKons (such as ++ , + = ) are considered as consisKng of two
basic operaKons
- The execuKon Kme of the method itself may depend on the value of parameter and it may not be constant
- To simplify complexity analysis we will not consider memory access (fetch or store) operaKons
14
 Algorithm Complexity: Growth FuncKons
- ComputaKonal complexity is a measure of the degree of difficulty of an algorithm
- It indicates how much effort is needed to apply an algorithm or how costly it is
- This cost can be measured in a variety of ways
- We must decide what we are trying to efficiently opKmize
- %me complexity – CPU Kme
- space complexity – memory space
- CPU Kme is generally the focus
- The rates of growth are expressed as funcKons, which are generally in terms of the
number of inputs n
- A growth funcKon shows the relaKonship between the size of the problem (n) and the
value we hope to opKmize (!me or space)
- This funcKon represents the Kme or space complexity of the algorithm 15
 Algorithm Complexity: Growth FuncKons (cont.)
Important Growth FuncKons:
- There are seven funcKons that oSen appear in
algorithm analysis:
- Constant funcKon: f(n) = c
- Logarithmic funcKon: f(n) = log n
- Linear funcKon: f(n) = n
- N-Log-N funcKon: f(n) = n log n
- QuadraKc funcKon: f(n) = n 2
- Cubic funcKon: f(n) = n 3
- ExponenKal funcKon: f(n) = 2n
- In a log-log plot, the slope of the line corresponds to
the growth rate of the funcKon
16
 Algorithm Complexity: The Cases
- Worst Case Complexity:
- The funcKon defined by the maximum
number of steps taken on any instance
of size n 500
Wort Case

Number of Steps (Cost), f (n)

➔ maximum over inputs of size n 400
Average Case
- Best Case Complexity: 300
- The funcKon defined by the minimum Best Case
number of steps taken on any instance 200
of size n
➔ minimum over inputs of size n 100

- Average Case Complexity: 0

- The funcKon defined by the average

number of steps taken on any instance
of size n
5 10 15 20

Problem/Input Size, n
➔ average over inputs of size n
17
 Algorithm Complexity: The Cases (cont.)
Example: Linear Search Complexity
- Best Case: Item found at the beginning
- One comparison
- Worst Case: Item found at the end
- n comparisons
- Average Case: Item may be found at index 0, or 1, or 2, . . . or n - 1
- Average number of comparisons is: (1 + 2 + . . . + n)/n = (n + 1)/2

18
 Algorithm Complexity: The Strategy
- We are usually interested in determining
the largest number of operaKons that might n0
be performed for a given problem size
- Best case depends on the input

Complexity ( f (n) ) →
- Average case is difficult to compute actual running
time
- So, we usually focus on worst case analysis
- Easier to compute
- Usually close to the actual running Kme
- Crucial to real-Kme systems (e.g. air-
traffic control)
Strategy: Input size ( n ) →
- Try to find upper and lower bounds of the Upper and Lower Bounds for n > n0
worst-case funcKon
19
 02

Today’s 01 Asymptotic Complexity

Asymptotic notations, rules and comparisons

Agenda Intro to Algorithm Analysis

Concept of running time and growth functions
Running Time Analysis
n Data Items
10010101000100100
10010010101000101
➔ ➔ Returns in time T1(n)
0000100100100

Algorithm 1
n Data Items
10010101000100100 ➔ ➔ Returns in time T2(n)
10010010101000101
0000100100100

Running Time T(n)

Algorithm 1
Algorithm 2

For very large n, algorithm 1 Algorithm 2

grows faster than algorithm 2
n0 Number of Input Item n
Problem size
21
 AsymptoKc Complexity
- It is not typically necessary to know the “exact” growth funcKon for an algorithm
- Finding the exact complexity, f(n) = number of basic operaKons, of an algorithm is
difficult
- We are mainly interested in the asymptoKc complexity of an algorithm
- the general nature of the algorithm as n increases
- AsymptoKc analysis of an algorithm describes the relaKve efficiency of an algorithm
as n get very large
- When you're dealing with small input size, most of algorithms will do
- When the input size is very large things change!

22
 AsymptoKc Complexity (cont.)
Growth Rates vs. n Size

* Assuming: 1 GHz CPU and that it can execute on average one instrucKon in 1 nanosecond
23
 AsymptoKc Complexity (cont.)
- AsymptoKc complexity is based on the dominant term of the growth funcKon
- The term that increases most quickly as n increases

- We approximate f(n) by a funcKon g(n) in a way that does not substanKally change the
magnitude of f(n)
- The funcKon g(n) is sufficiently close to f(n) for large values of the input size n
- This "approximate" measure of efficiency is called asymptoKc complexity
- It does not give the exact number of operaKons of an algorithm, but it shows how that
number grows with the size of the input
- This gives us a measure that will work for different operaKng systems, compilers and CPUs
- AsymptoKc bounds are used to esKmate the efficiency of algorithms by assessing the
amount of Kme and memory needed to accomplish the task for which the algorithms
were designed
24
 AsymptoKc NotaKons
- AsymptoKc notaKons are mathemaKcal notaKons used to describe the running Kme of an
algorithm when the input tends towards a parKcular value or a limiKng value
- The most commonly used asymptoKc notaKons are:
- O (oh) NotaKon
- O(expression) gives an upper bound on the growth rate of a funcKon
- It describes the worst-case scenario or the longest amount of Kme an algorithm can possibly
take to complete
- × (omega) NotaKon
- ×(expression) gives a lower bound on the growth rate of a funcKon
- It measures the best-case scenario or the shortest amount of Kme an algorithm can possibly
take to complete
- − (theta) NotaKon
- −(expression) consist of all the funcKons that lie in both O(expression) and ×(expression)
- It indicates that the upper and lower bounds are the same within a constant factor
25
 Big-O NotaKon
Big O, DefiniKon:
- f(n) = O(g(n)) if and only if there are posiKve constants c and n0 such that f(n) × c g(n)
when n − n0
- This says that funcKon f(n) grows, asymptoKcally, at a rate no faster than g(n) and up to
a constant factor
- Thus g(n) is an upper bound on f(n)
Another way:
f(n) is O(g(n)) ↔ there exist numbers c, n0 > 0
such that for each n ≥ n0
f(n) ≤ c.g(n)

26
Big-O NotaKon: IllustraKon

c . g(n)
f(n)

n0 n
f(n) = O(g(n))
Growth f(n) is × growth of g(n)
27
 Big-× NotaKon
Big ×, DefiniKon:
- f(n) = ×(g(n)) if and only if there are posiKve constants c and n0 such that
f(n) − c g(n) when n − n0
- This says that funcKon f(n) grows, asymptoKcally, at a rate no slower than g(n)
- Thus g(n) is a lower bound on f(n)
Another way:
f(n) is Ω(g(n)) ↔ there exist numbers c, n0 > 0
such that for each n ≥ n0
f(n) ≥ c.g(n)

28
Big-× NotaKon: IllustraKon

f(n)

c . g(n)

n0 n
f(n) = ×(g(n))
Growth f(n) is − growth of g(n)
29
 Big-× NotaKon
Big ×, DefiniKon:
- f(n) = ×(g(n)) if and only if f(n) = O(g(n)) and f(n) = −(g(n))
- This says that funcKon f(n) grows, asymptoKcally, at the same rate as g(n)
Another way:
f(n) is θ(g(n)) ↔ there exist numbers c1, c2, n0 > 0
such that for each n ≥ n0
c1.g(n) ≤ f(n) ≤ c2.g(n)

big-− notation big-O notation

30
Big-× NotaKon: IllustraKon

cc2 .⋅ g(n)
g(n)
2
f(n)
f(n)

cc1⋅. g(n)
g(n)
1

nN0 nn
f(n) = ×(g(n))
Growth f(n) is = growth of g(n)
31
AsymptoKc NotaKons Summary

Asymptotic
Mathematical Expression Relative Rates of Growth
Notation

f(n) is O(g(n)) if one only if f(n) is

Big-Oh f(n) = O(g(n)) × f(n) − g(n)
asymptotically less than or equal to g(n)

f(n) is Ω(g(n)) if one only if f(n) is

Big-Omega f(n) = Ω(g(n)) × f(n) Θ g(n)
asymptotically greater than or equal to g(n)

f(n) is Θ(g(n)) if one only if f(n) is

Big-Theta f(n) = ≤(g(n)) × f(n) = g(n)
asymptotically equal to g(n)

32
 Big-Oh Rules
- Remember that Big-Oh is simplified analysis of an algorithm’s efficiency
- When using big-oh notaKon, the following simplificaKon rules can be applied:
Rule 1: Ignore constant factors
- O( c . f(n) ) = O( f(n) )
- If f(n) is a product of several factors, any constants can be omiVed
- Examples:
- O(5n) = O(n)
- O(300n 2) = O(n 2)

33
 Big-Oh Rules (cont.)
Rule 2: Simplify polynomial funcKons
- If a funcKon f(n) is a polynomial of degree d, then f(n) is O(n d)
- Examples:
- O(n 3 + 3n 2 + 4n + 6) = O(n 3)
- O(21n 8 + 33n 5 + 4n 2 + 6) = O(n 8)

34
 Big-Oh Rules (cont.)
Rule 3: Ignore smaller terms
- If f(n) is a sum of several terms, only keep the one with the largest growth rate
- Examples:
- O(3n log n + 5 log n + 10n + 6) = O(n log n)
- O(n 3 + 2n 2 + 3n log n + 7) = O(n 3)
- O(2000n 3 + 2n! + n 800 + 10n + 27n log n + 5) = O(n!)

35
 Big-Oh Rules (cont.)
Rule 4: Ignore logarithms base
- loga n = O(logb n)
- For any a and b that are greater than one
- Example:
- O(3 log3 n + 2 log4 n) = O(log n) NOT O(log3 n)

36
 Big-Oh Rules (cont.)
Rule 5: AddiKon Rule
- O( f(n)) + O(g(n)) = O( max( f(n), g(n)) )
- If an algorithm takes O( f(n) + g(n)) steps and funcKon f(n) is bigger than g(n), then
algorithm’s performance can be simplified to O( f(n))
- Example1:
- f(n) = n 2, g(n) = n 3
- O( f(n) + g(n)) = O(max(n 2, n 3)) = O(n 3)
- Example2:
- f(n) = n 3 + n 2 log n × O(n 3)
- g(n) = n 3 + 2n! + 10n × O(n!)
- O( f(n) + g(n)) = O(max(n 3, n!)) = O(n!)
37
 Big-Oh Rules (cont.)
Rule 6: MulKplicaKon Rule
- O( f(n)) × O(g(n)) = O( f(n) × g(n))
- If an algorithm performs an operaKon that takes f(n) steps, and for every step
performs another operaKon that takes g(n) steps, algorithm’s total performance is
O( f(n) × g(n))
- Example:
- f(n) = n 3 + 2n 2 + 3n log n + 7 − O(n 3)
- g(n) = 8n 2 + 5n + 2 − O(n 2)
- O( f(n) × g(n)) = O((n 3) × (n 2)) = O(n 5)

38
 Big-Oh Rules (cont.)
Rule 7: Tight bounding
- Always use the smallest possible class of funcKons to bound an algorithm
- f(n) = 2n × O(n) instead of O(n 2)
- f(n) = n + (log n − log n) × O( n) instead of O(n 2)

39
 Comparing Growth FuncKons
- You might think that faster processors would make efficient algorithms less important
- A faster CPU helps, but not relaKve to the dominant term
Affect on an algorithm that runs for a few seconds
Growth Rate
Time after 100x more data Problem size after 100x speedup
n A few minutes 100x
n2 Several hours 10x
n3 Several weeks 4-5x
2n Forever 1x

- So the common pracKce is to establish a relaKve order among different algorithms, in

terms of their relaKve rates of growth
- The rates of growth are expressed as funcKons, which are generally in terms of the
number of inputs n
40
 Comparing Growth FuncKons (cont.)

(A Hierarchy of Growth Rate)

Logarithmic ＜ Polynomial ＜ Exponential ＜ Factorial

c < log4 n < log3 n < log2 n < log2 n < logk n < n < n < n log2 n < n 2 < n 3 < 2n < 3n < n! < n n

41
Comparing Growth FuncKons (cont.)

Big-O Complexity Chart

As n increases, the various growth functions diverge dramatically 42
 Comparing Growth FuncKons (cont.)
- You can compare growth funcKons to find their asymptoKc relaKonship
- Remember, when you’re comparing two funcKons, if there is anything common
between them, cancel it out

f(n) = n 2 g(n) = n 3

n2 n3 → Divide both functions by n 2

1 n →1 < n
g(n) grows faster than f(n) × f(n) = O(g(n)) OR g(n) = −( f(n))

- AlternaKvely, you can subsKtute with a large value of n in both funcKons and compare
the numeric results
43
 Comparing Growth FuncKons (cont.)
- Example: Which of the following funcKons grows faster?

f(n) = n log n g(n) = n 1.5

n log n n 1.5 → Divide both functions by n

log n n 0.5 → Raise both sides to the power of 2

log2 n n → log2 n < n

g(n) grows faster than f(n) × f(n) = O(g(n)) OR g(n) = −( f(n))

Q: Which one executes faster?!

44
 Comparing Growth FuncKons (cont.)
- Another example
f(n) = 2n g(n) = n 2

2n n2 → Apply log to both sides

log 2n log n 2 → log a b = b log a

n log 2 2 log n → log2 2 = 1

n 2 log n → n > 2 log n

f(n) grows faster than g(n) × g(n) = O( f(n)) OR f(n) = −(g(n))
45
 Comparing Growth FuncKons (cont.)
- One more:
f(n) = 3n g(n) = 2n

3n 2n → Apply log to both sides

n log 3 n log 2 → Divide both functions by n

log 3 log 2 → f(n) × g(n)

f(n) and g(n) grow at similar rate − f(n) = Ω(g(n))

- Note that log 3 < log 2 numerically, but asymptoKcly they are the same
46
 Big-Oh Categories & ImplicaKons
Class Name Practical Implication
Common Big-Oh categories and pracKcal

O(1) constant Independent of input size

O(log log n) bi-logarithmic or log log n
implicaKons of order-of-growth

O(log n) logarithmic or log n

Nearly independent of input size
O((log n)k) or O(logkn) poly-logarithmic
O(n0.5)
O(n) linear Optimal for n inputs
O(n log n) linear logarithmic or n-log-n Nearly optimal for n inputs
O(n2) quadratic
Not practical for large problems
O(n2 log n) quadratic logarithmic
O(n3) cubic Not practical for medium problems
O(2n) base-2 exponential
O(en) natural exponential
O(3n) base-3 exponential Useful only from tiny problems
O(n!) factorial
O(nn) hyper-exponential
47
Big-Oh Cheat Sheet

Big-O complexities of common algorithms used in Computer Science

<[Link] 48
 03

02 Code Complexity
Finding complexity of code structures

Today’s 01 Asymptotic Complexity

Asymptotic notations, rules and comparisons

Agenda Intro to Algorithm Analysis

Concept of running time and growth functions
 Code Complexity
- Determining the complexity of some code structures is a common pracKce in
algorithm analysis
- In general,
- doing something with every item in one dimension is linear
- doing something with every item in two dimensions is quadraKc, and
- dividing the working area is logarithmic (of the divisor)

50
 Analyzing Loop ExecuKon
Loops: for, while, and do-while
- Loops complexity is determined by the number of iteraKons in the loop mulKplied by
the complexity of the body of the loop
- Loop complexity = Number of iteration × Body complexity
- Examples:
Number of loop executions = n
for (int count = 0; count < n; count++)
//some sequence of O(1) steps ➡ Body complexity = O(1)
Loop complexity = n × O(1) = O(n)

Number of loop executions = n 2

for (int i = 0; i < n*n; i++)
sum = sum + i; ➡ Body complexity = O(1)
Loop complexity = n 2 × O(1) = O(n 2)
51
 Analyzing Loop ExecuKon (cont.)
- We start by considering how to count operaKons in for-loops
- First, we should know the number of iteraKons of the loop; say it is x. Then:
- The loop condiKon is executed x + 1 Kmes
- Each of the statements in the loop body is executed x Kmes
- The loop-index update statement is executed x Kmes
- Example:
Time units to compute:
int sum (int n) • 1 for the assignment
{ • Loop Statement: 1 assignment, n + 1
int partial_sum = 0; tests, and 2n increments
int i;
for (i = 1; i <= n; i++)
partial_sum = partial_sum + (i * i);
➡ • Loop Body:
• n loops of 3 units (an assignment,
an addition, and multiplications)
return partial_sum; • 1 for the return statement
} Total: 1 + (1 + n + 1 + 2n) + 3n + 1
= 6n + 4 = O(n)
52
 Analyzing Loop ExecuKon (cont.)
- Another example:
- Find the exact number of basic operaKons in the following program fragment:
Basic operations to consider:
• 2 operations for the assignments outside the loop
• Loop Statement:
• 1 assignment (i=0),
double x, y;
• n + 1 operations for the condition test (i<n),
x = 2.5 ; y = 3.0;
• 2n operations for the increment (i++)
for(int i = 0; i < n; i++){
a[i] = x * y;
x = 2.5 * x;
➡ • Loop Body:
• n loops of:
• 3 assignments,
y = y + a[i];
• 2 multiplications,
}
• 1 addition
→ 6n operations
Total number of basic operations is:
6n + 2n + (n + 1) + 3 = 9n + 4 = O(n)
53
 Analyzing Loop ExecuKon (cont.)
- One more example:
Basic operations to consider:
• The number of iterations is:×(n − k)/mΩ
for(int i=k; i<n; i=i+m){ • The initialization statement, i = k, is executed 1 time
• The condition, i < n, is executed ×(n − k)/mΩ + 1 times
➡
statement1;
statement2; • The update statement, i = i + m, is executed
} ×(n − k)/mΩ times
• Each of statement1 and statement2 is executed
×(n − k)/mΩ times
- What about?
for(int i=k; i<=n; i=i+m){
statement1;
statement2;
}
54
55
 Analyzing Loop ExecuKon (cont.)
Loops with logarithmic IteraKons:
- Loops that iteraKvely divide the work space have a logarithmic running Kme
- Examples:
for (int i = k; i < n; i = i * m)
//some sequence of O(1) steps ➡ Number of iterations: logm(n × k)

for (int i = k; i <= n; i = i * m)

//some sequence of O(1) steps ➡ Number of iterations: logm(n × k) + 1

for (int i = 0; i < n; i = i * 2)

//some sequence of O(1) steps ➡ O(log n)
56
55
 Analyzing Loop ExecuKon (cont.)
- More examples:
count = 1;
while (count < n){
count *= 2;
//some sequence of O(1) steps
➡ O(log n)
}

while (n > 1){

}
n = n / 2;
//some sequence of O(1) steps ➡ O(log n)

56

57
56
 Analyzing Loop ExecuKon (cont.)
Netsted loops:
- When loops are nested, we mulKply the complexity of the outer loop by the
complexity of the inner loop
- Nested loops complexity = complexity of inner loop × complexity of outer loop
- Examples:
for (int count=0; count<n; count++) Both the inner and outer loops
n
n
for (int count2=0; count2<n; count2++)
// some sequence of O(1) steps ➡ have complexity of O(n)
The overall efficiency is O(n 2)

sum = 0

n 2
for(int i = 0; i < n*n; i++)
n for(int j = 0; j < n; j++)
sum += i * j ;
➡ O(n ) 3

58
57
 Analyzing Loop ExecuKon (cont.)
- More examples:
i = 1;
while(i <= n) {
j = 1;
while(j <= n){
n
log n
}
//statements of constant complexity
j = j*2; ➡ O(n log n)
i = i+1;
}

n for(int i = 1; i <= n; i++)

m for(int j = 1; j <= m; j++)
sum = sum + i + j; ➡ O(mn)
n for(int i = 1; i <= n; i++)
m for(int j = 1; j <= m; j++)
p for(int k = 1; k <= p; k++)
sum = sum + i + j + k;
➡ O(pmn)
59
58
 Analyzing Sequence of Statements
ConsecuKve statements:
- Use addiKon rule ➔ the maximum is the one that counts
- O( f1, f2, …, fk) = O( f1) + O( f2) + … + O( fk) = O(max( f1, f2, …, fk))
- Example:
n 2 for (int j = 0; j < n * n; j++)
sum = sum + j; Complexity: O(n 2) + O(n) + O(1)
n for (int k = 0; k < n; k++)
sum = sum - l;
➡ = O(max(n 2, n, 1))
= O(n 2)
1 [Link]("sum is now ” + sum);

60
59
 Analyzing Sequence of Statements (cont.)
- More example:
n for (i = 1; i <= n; i++)
sum = sum + i; Complexity: O(n) + O(n 2)

n2
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++)
sum = sum + i + j;
➡ = O(max(n, n 2))
= O(n 2)
}

3
for (i = 1; i <= n*n; i++)
Complexity: O(n 3) + O(1) + O(n 2) + O(n)
n for (j = 1; j <= n; j++)
sum = sum + i + j; = O(max(n 3, 1, n 2, n))
1 sum = sum / n; = O(n 3)
n2
for (i = 1; i <= n*n; i++)
sum = sum + i;
➡ OR: O(n 3) + O(1) + O(n 2) + O(n)
for (j = 1; j <= n; j++)
= O(n 3 + n 2 + n + 1)
n = O(n 3)
sum = sum + j * j;
61
60
 Analyzing CondiKonal Statements
CondiKons: if-else, switch
- Take the complexity of the most expensive case
- if(test) s1 else s2
- The running Kme is never more than the running Kme of the test plus the larger of
the running Kmes of s1 and s2
- Example:
1 if (test == 1)
for (i = 1; i <= n; i++)
n
sum = sum + i;
Running time = 1 + max(n, n 2)

n2
else
for (i = 1; i <= n; i++)
➡ = O(n 2)
for (j = 1; j <= n; j++)
sum = sum + i + j;
61
62
 Analyzing CondiKonal Statements (cont.)
- if-else Example:
char key;
int[][] A = new int[n][n];
int[][] B = new int[n][n];
int[][] C = new int[n][n];
: : :
2
n if(key == ‘+') {
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
C[i][j] = A[i][j] + B[i][j];
➡ Overall Complexity: O(n 3)

} // End of if block
3 else if(key == 'x')
n
C = matrixMult(A, B);
1 else
[Link]("Error! Enter '+' or 'x'!");

63
62
64
+ (max O(n2,n))

65
66
 Analyzing Method Calls
- The body of a loop may contain a call to a method
- To determine the order of the loop body, the order of the method must be taken into
account
- The overhead of the method call itself is generally ignored
- Loop example:
static int myMethod(int n){
int sum = 0;
log n for(int i = 1; i < n; i = i * 2)
sum = sum + i + helper(i);
return sum; n
}
static int helper(int n){
int sum = 0;
➡ Complexity of myMethod(): O(n log n)

n for(int i = 1; i <= n; i++)

sum = sum + i;
return sum;
} 67
64
68
Review of Common Order-of-Growth Hypotheses

65
69
 Example Algorithms’ ComplexiKes
- Examples of Algorithms and their big-O complexity
Big-O Notation Example Algorithms
Push, Pop, Enqueue (if there is a tail reference),
O(1)
Dequeue, Accessing an array element
O(log(n)) Binary search
O(n) Linear search
O(n log(n)) Heap sort, Quick sort (average), Merge sort
O(n2) Selection sort, Insertion sort, Bubble sort
O(n3) Matrix multiplication
O(2n) Towers of Hanoi
66
70
 04

03 Finishing Thoughts
Summary & resources

02 Code Complexity
Finding complexity of code structures

Today’s 01 Asymptotic Complexity

Asymptotic notations, rules and comparisons

Agenda Intro to Algorithm Analysis

Concept of running time and growth functions
Important to Remember…
SoSware must make efficient use of resources such as CPU Kme and memory.
Algorithm analysis is a fundamental computer science topic.
A growth funcKon shows Kme or space uKlizaKon relaKve to the problem size.
The order of an algorithm is found by eliminaKng constants and all but the dominant
term in the algorithm’s growth funcKon.
The order of an algorithm provides an upper bound to the algorithm’s growth funcKon.
If the algorithm is inefficient, a faster processor will not help in the long run.
Analyzing algorithm complexity oSen requires analyzing the execuKon of loops.
The Kme complexity of a loop is found by mulKplying the complexity of the body of the
loop by how many Kmes the loop will execute.
The analysis of nested loops must take into account both the inner and outer loops.
If and Switch statements: take the complexity of the most expensive case.
If there are funcKon calls, these must be analyzed first.
72
68
Resources & More…

Textbooks Chapters:
- Data Structures and Algorithms in Java, Ch2
- Data Structures and Algorithm Analysis in Java, Ch2
Short Videos:
- What Is Big O? (Comparing Algorithms)
- Big-O notation in 5 minutes
- #2.4- ‫ ﺷﺮح ﻣﻔﻬﻮم اﻟـ‬Big O - Notation
Credits:
- Some slides illustrative content is courtesy of Prof.
Robert Sedgewick, Princeton University
73
69
Resources & More…

Other Resources:
- Java Software Structures, - Designing and Using Data
Structures,4th edition, Lewis and Chase
- Data Structures and Problem Solving Using Java, 4th edition, Weiss
- Data Structures & Algorithms in Java, 3rd edition, Drozdek
- Data Structures and Algorithm Analysis in Java, 3rd edition, Weiss
- Algorithms, 4th edition, Sedgewick and Wayne
- A Practical Introduction to Data Structures and Algorithm Analysis,
3rd edition, Shaffer
- Data Structures and Algorithms in Java, 6th edition, Goodrich,
Tamassia and Goldwasser
- Slides at: [Link]
74
70
Resources & More…

Good Reads:
- How to find time complexity of an algorithm?
- 8 time complexities that every programmer should know
- Understanding Time Complexity with Simple Examples
- Analysis of Algorithms | Set 3 (Asymptotic Notations)
- Analysis of Algorithms | Set 4 (Analysis of Loops)
- Practice Questions on Time Complexity Analysis

75
71
Thank You & Stay Safe
:)