CITY COLLEGE OF SAN FERNANDO PAMPANGA
City of San Fernando, Pampanga
INSTITUTE OF INFORMATION TECHNOLOGY
DATA STRUCTURES AND ALGORITHMS
Module 4: Time and Space Complexity
Learning Outcomes:
At the end of the module, the students are able to:
● Define Time Complexity and Space Complexity.
● Interpret Big O Notation and common complexity classes.
● Analyze the complexity of given algorithms.
● Implement and test algorithms in Java to measure execution time and memory usage.
Module Description:
Time and Space Complexity are critical concepts in computer science used to evaluate the efficiency
of algorithms. They help developers choose the right algorithm for a given problem based on speed
and memory usage. In this lesson, students will learn how to analyze algorithms, interpret Big O
notation, and apply it to Java code.
III. Lesson Content
1. Introduction to Algorithm Efficiency
● What it means:
Every algorithm solves a problem, but some do it faster or use less memory than others.
Time complexity measures how much time an algorithm takes to run as the size of the input
changes.
Space complexity measures how much memory it needs during execution.
● Why it matters:
In real-world applications like web search, banking transactions, or mobile apps, speed and
memory usage are critical. An inefficient algorithm can cause slow apps or even system
crashes.
2. Time Complexity
Data Structures and Algorithms Page 1 | 4
CITY COLLEGE OF SAN FERNANDO PAMPANGA
City of San Fernando, Pampanga
INSTITUTE OF INFORMATION TECHNOLOGY
● Definition:
Time complexity is expressed as a function of input size n, using Big O notation (e.g., O(1),
O(n), O(n²)). It represents the upper bound on the running time.
● Purpose:
o Helps compare algorithms without actually running them.
o Predicts performance for large data sets.
● Common Time Complexities:
Notation Name Example Scenario
O(1) Constant Time Accessing an element in an array by index
O(log n) Logarithmic Time Binary search
O(n) Linear Time Traversing a list
O(n log n) Log-linear Time Merge sort
O(n²) Quadratic Time Bubble sort, nested loops
O(2ⁿ) Exponential Time Solving the traveling salesman problem by brute force
● Example in Java (Linear Search):
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < [Link]; i++) {
if (arr[i] == target) {
return i; // Found at index i
}
}
return -1; // Not found
}
Analysis:
o Worst case: O(n) (must check every element)
o Best case: O(1) (target is the first element)
3. Space Complexity
● Definition:
The amount of memory required by an algorithm, including:
1. Fixed Part: Memory for constants, program code, and fixed-size variables.
2. Variable Part: Memory for dynamic allocations, recursion stack, and data
structures.
● Factors Affecting Space Complexity:
o Size of the input
o Temporary variables and data structures
Data Structures and Algorithms Page 2 | 4
CITY COLLEGE OF SAN FERNANDO PAMPANGA
City of San Fernando, Pampanga
INSTITUTE OF INFORMATION TECHNOLOGY
o Recursion depth
● Example in Java (Recursion Stack Usage):
public static int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}
Analysis:
o Space Complexity: O(n) because each recursive call adds a new frame to the call
stack.
4. Big O, Big Ω, and Big Θ Notations
● Big O (O): Worst-case scenario (upper bound) — how slow it could be.
● Big Ω (Omega): Best-case scenario (lower bound) — how fast it could be.
● Big Θ (Theta): Average-case scenario — the "expected" performance.
● Example:
In linear search:
o Best Case: O(1) (target is first element)
o Worst Case: O(n) (target is last element or absent)
o Average Case: O(n/2) → O(n) (on average, half the elements are checked)
5. Trade-offs Between Time and Space
● Sometimes faster algorithms require more memory, and vice versa.
● Example:
o Storing precomputed results in a lookup table → Faster but uses more space.
o Computing results on the fly → Slower but uses less space.
6. Real-World Importance
● Web search engines: Need fast algorithms to handle billions of searches per second.
● Gaming: AI computations must be optimized for speed to avoid lag.
● Mobile apps: Limited RAM means algorithms must be space-efficient.
Data Structures and Algorithms Page 3 | 4
CITY COLLEGE OF SAN FERNANDO PAMPANGA
City of San Fernando, Pampanga
INSTITUTE OF INFORMATION TECHNOLOGY
References (APA 7th ed.)
● Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms (4th
ed.). MIT Press.
● Liang, Y. D. (2020). Introduction to Java programming and data structures (12th ed.).
Pearson.
● Oracle. (2024). The Java™ tutorials. [Link]
● Wirth, N. (2020). Algorithms and data structures. Springer.
Data Structures and Algorithms Page 4 | 4