Big-O Notation – Runtime Complexity & Algorithm Efficiency

This post is a term explanation of Big-O notation – including exam questions and tags.

In a Nutshell

Big-O notation describes how strongly the runtime or memory requirement of an algorithm grows in relation to the input size – it is a measure of efficiency.

Compact Technical Description

Big-O notation is used to analyze the asymptotic complexity of an algorithm – it abstracts from concrete runtimes and focuses on behavior as input grows. In the worst case (“Worst Case”), it specifies the number of computational steps or memory accesses an algorithm requires. Examples: O(1) = constant, O(n) = linear, O(n²) = quadratic, O(log n) = logarithmic. This allows algorithms to be compared independently of hardware.

Exam-Relevant Key Points

• Big-O describes the growth behavior of runtime/memory
• “Worst Case” is considered by default
• Typical notations: O(1), O(n), O(log n), O(n²), O(n log n)
• Logarithmic, for example, in binary search (IHK-relevant)
• Quadratic algorithms are inefficient with large data
• Efficient algorithms save resources → economically relevant
• Big-O analysis must be documented in complex algorithms

Core 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
10. Relevance for Scalability

Practical Example

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

Explanation: Linear search traverses the list completely, binary search halves the search field at each step – much more efficient with large amounts of data.

Advantages and Disadvantages

Advantages

• Comparability of algorithms independent of implementation
• Detection of potential bottlenecks
• Better decisions in design phases

Disadvantages

• No statements about concrete runtimes on specific hardware
• Only Worst-Case without considering averages
• Theoretical, not always directly transferable to real conditions

Typical Exam Questions (with Short Answer)

1. Big-O notation describes? Complexity of an algorithm in relation to runtime or memory requirement as input grows.
2. What does O(1) mean? Runtime is constant – independent of input size.
3. More efficient: O(n) or O(log n)? O(log n), because it is significantly faster as data volume increases.
4. What does “n” stand for in O(n)? Number of input elements.
5. Algorithm typically O(n log n)? Merge Sort or Quick Sort on average.
6. Why is O(n²) problematic? Runtime grows exponentially with large data volumes.
7. Both O(n) and O(n²) simultaneously? No – the dominant component is always specified.
8. Document Big-O? Through code comments, diagrams, or formal analysis.

Most Important Sources

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