Big-O Notation – Algorithm Runtime Complexity & Efficiency

This article is a concept explainer on Big-O notation, complete with exam questions and key points.

In a Nutshell

Big-O notation describes how the runtime or memory requirements of an algorithm scale relative to the input size—it’s a measure of algorithmic efficiency.

Core Technical Definition

Big-O notation is used to analyze the asymptotic complexity of an algorithm. It abstracts away concrete execution times and focuses on behavior as input grows. The worst-case scenario determines the number of computational steps or memory accesses required. Common examples: O(1) = constant, O(n) = linear, O(n²) = quadratic, O(log n) = logarithmic. This allows you to compare algorithms independent of hardware.

Key Exam Concepts

• Big-O describes growth behavior of runtime and memory
• Worst case is analyzed by default
• Typical notations: O(1), O(n), O(log n), O(n²), O(n log n)
• Logarithmic complexity appears in binary search
• Quadratic algorithms become inefficient with large datasets
• Efficient algorithms reduce resource consumption and have economic value
• Big-O analysis should be documented for complex algorithms

Main Components

1. Constant: O(1)
2. Linear: O(n)
3. Logarithmic: O(log n)
4. Linear-logarithmic: O(n log n)
5. Quadratic: O(n²)
6. Cubic: O(n³)
7. Exponential: O(2ⁿ)
8. Worst-case analysis
9. Best-case, average-case analysis
10. Relevance for scalability

Practical Example

// Comparison: linear vs. binary search
Linear search: O(n)
Binary search: O(log n), only on sorted lists

Explanation: Linear search iterates through the entire list, while binary search halves the search space at each step—much more efficient with large datasets.

Strengths and Limitations

Strengths

• Compare algorithms regardless of implementation details
• Identify potential bottlenecks early
• Make better architectural decisions during design

Limitations

• Says nothing about concrete runtime on specific hardware
• Focuses on worst case without considering averages
• Theoretical; doesn’t always map directly to real-world conditions

Common Exam Questions (with Brief Answers)

1. What does Big-O notation describe? Algorithm complexity in terms of runtime or memory requirements as input grows.
2. What does O(1) mean? Runtime is constant—independent of input size.
3. Which is more efficient: O(n) or O(log n)? O(log n), because it scales much better as data volume increases.
4. What does “n” represent in O(n)? The number of input elements.
5. Which algorithm is typically O(n log n)? Merge Sort or Quick Sort on average.
6. Why is O(n²) problematic? Runtime grows quadratically with large datasets.
7. Can an algorithm be both O(n) and O(n²) simultaneously? No—always express the dominant component.
8. How do you document Big-O analysis? Through code comments, diagrams, or formal analysis documentation.

Essential Resources

1. https://www.bigocheatsheet.com/
2. https://visualgo.net/en
3. https://www.geeksforgeeks.org/analysis-of-algorithms-set-1-asymptotic-analysis/
4. https://cs50.harvard.edu/
5. https://www.youtube.com/results?search_query=big+o+notation