Week 2 The Core
of Efficiency
Measuring performance in
Python.
Algorithm
Big-O Notation • Case
Analysis • Space-Time
Trade-offs
Analysis &
Complexity
Measuring Growth
Time complexity measures how execution
time grows with input size (n). We focus on
the dominant term as n becomes very large.
Input (n ) O(n) O(n²)
10 10 ops 100 ops
100 100 ops 10,000 ops
1,000 1,000 ops 1,000,000 ops
Time
Complexity
Memory Usage Efficiency
Space complexity measures the total memory
an algorithm uses relative to input size (n).
Fixed Space: Constants, simple variables,
and fixed-size structures. O 1
Variable Space: Dynamic arrays, recursion
stacks, and input-dependent structures.
O(n)
Python Note: Consider the overhead of
objects and dynamic lists.
Space
Complexity
The Upper Bound
Big-O O -
describes the worst case scenario or
the upper bound of growth . It guarantees that
an algorithm will never perform worse than this
limit .
Common Classes: O 1 , O(log n), O(n), O(n log n),
O(n²)
Big-O Notation
Lower and Tight Bounds
While Big-O provides an upper bound, other
notations describe different aspects of growth.
Big-Ω (Omega): The lower bound. It describes
the best-case scenario or minimum growth rate.
Big-Θ (Theta): The tight bound. It describes the
exact growth rate when upper and lower
bounds match.
Big-Ω and Big-
Θ If f(n) = O(g(n)) AND f(n) = Ω(g(n)), then f(n) =
Θ(g(n)).
Best, Average, and Worst
Algorithms perform differently based on input.
We analyze three scenarios:
Worst-Case:
The maximum time required. This is our
standard for reliability.
Best-Case:
The minimum time required (e.g., finding the
item at index 0 .
Average-Case:
The expected time over all possible inputs.
Case Analysis
Example: Linear Search
Worst: O(n) • Best: O 1 • Average: O(n/2) →
O( n )
A Visual Guide
Different complexity classes diverge rapidly as
input size n grows Choosing the right class is
.
critical for scalability .
Complexity O 1 : Constant • O(log n): Logarithmic
Classes
O(n): Linear • O(n log n): Linearithmic
O(n²): Quadratic • O 2ⁿ): Exponential
Simple Loops in Python
To determine complexity, we analyze the growth of
operations relative to the input size n.
def f nd_sum(arr)
total = 0 # O(1)
for x in arr: # n iterations
total += x # O(1)
return total # O(1)
Total: O(n)
Rules:
[Link] time operations are O 1 .
2. Consecutive statements are added.
3. Loops multiply complexity by iterations.
Code Analysis
Nested Loops & Conditionals
Nested structures result in multiplied complexities,
while branching logic requires worst-case
consideration.
def print_pairs(arr)
for i in arr: # n iterations
for j in arr: # n iterations
print(i, j) # O(1)
Total: O(n * n) = O(n²)
Rules:
[Link] loops multiply (n * n = n²).
2. For conditionals, take the "heavier" branch.
3. Drop lower-order terms (e. g., n² + n → n²).
Nested Logic
Identifying Complexity
Analyze the following Python snippets. What is their
Big-O complexity?
Snippet 1
def get_f rst(arr)
return arr[0] if arr else None
Snippet 2
def print_all(arr)
for item in arr:
print(item)
Snippet 3
Practical
def print_pairs(arr)
for i in arr:
for j in arr:
print(i, j)
Activity
Complexity Determination
Determine the Time and Space Complexity for the
following algorithms. Provide a brief justification for
each.
Algorithm Time Space
Matrix Addition (n x n) ? ?
Recursive Fibonacci ? ?
Bubble Sort ? ?
Due Date: Before Week 3
Assignment
Week 2 Recap
✓ Big-O is our primary tool for comparing
algorithm efficiency.
✓ Focus on worst-case analysis for robust
software design.
✓ Asymptotic notations O, Ω, Θ) provide a
full performance spectrum.
Coming Up: Week 3
Summary &
Linear Data Structures: Linked Lists. We will
analyze their trade-offs vs. standard Python
lists and understand their memory efficiency.
Preview