Beginner LevelData Structures & Algorithms
What is Big-O Notation and why is it important?
ā Interview Prompt: Explain Big-O Notation, time vs space complexity, common complexity classes, and how to analyse simple algorithms.
Big-O Notation describes the worst-case upper bound on how an algorithm's runtime or memory usage grows relative to the input size $N$.
Common Complexity Classes (Best ā Worst):
| Notation | Name | Example |
|---|---|---|
| $O(1)$ | Constant | Hash map lookup |
| $O(\log N)$ | Logarithmic | Binary search |
| $O(N)$ | Linear | Array scan |
| $O(N \log N)$ | Linearithmic | Merge sort |
| $O(N^2)$ | Quadratic | Bubble sort |
| $O(2^N)$ | Exponential | Subsets generation |
| $O(N!)$ | Factorial | Permutation generation |
Analysis Rules:
ā¢
Drop constants: $O(2N) = O(N)$.
ā¢
Drop non-dominant terms: $O(N^2 + N) = O(N^2)$.
ā¢
Space complexity counts auxiliary memory (excluding the input itself).
Code Implementation Example
typescript
// O(N^2) ā nested loop, quadratic growth
function hasDuplicateNaive(arr: number[]): boolean {
for (let i = 0; i < arr.length; i++) // O(N)
for (let j = i + 1; j < arr.length; j++) // O(N)
if (arr[i] === arr[j]) return true;
return false;
}
// O(N) ā single-pass with a Set
function hasDuplicateOptimal(arr: number[]): boolean {
const seen = new Set<number>();
for (const n of arr) {
if (seen.has(n)) return true;
seen.add(n);
}
return false;
}š”Reducing a duplicate-check from O(NĀ²) to O(N) using a Set.
šÆ Interview Key Takeaway
Big-O is the universal language for comparing algorithm efficiency. Always analyse both time and space complexity when designing solutions.
#DSA#Big-O#Complexity#Analysis#Beginner
Back to all Data Structures & Algorithms Questionsā