🚀 Algorithm Complexity: Full Guide

1. What is Algorithmic Complexity?

Algorithmic complexity refers to how the performance (in terms of time and space) of an algorithm scales with input size n.

2. Time Complexity

Time complexity indicates the number of basic operations an algorithm performs. It is expressed using Big-O notation.

Common Time Complexities

Notation	Name	Example
O(1)	Constant	Accessing array element
O(log n)	Logarithmic	Binary Search
O(n)	Linear	Loop through array
O(n log n)	Linearithmic	Merge Sort
O(n²)	Quadratic	Nested loops
O(2ⁿ)	Exponential	Recursive subset generation

Example:


for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    console.log(i, j);
  }
}
// Time Complexity = O(n²)

3. Space Complexity

Space complexity refers to the memory used by the algorithm (excluding input size). It includes variables, function call stack, and data structures.


function sum(a, b) {
  let result = a + b;
  return result;
}
// Space Complexity: O(1)

Note: Recursive calls add to stack space.

4. Complexity Notations

Big-O (O): Worst case
Big-Ω (Omega): Best case
Big-Θ (Theta): Average case

5. How to Handle Large Inputs Efficiently

Use faster algorithms (e.g. O(n log n) instead of O(n²))
Choose optimal data structures (e.g., Set for lookup)
Use memoization/dynamic programming
Avoid unnecessary computations inside loops
In-place operations reduce space complexity

6. TLE (Time Limit Exceeded)

If your code exceeds the time limit of the online judge, it results in TLE. This often means the logic is right but inefficient.

Tip: Replace nested loops with prefix sums, binary search, or hash maps where possible.

7. Complexity Graph Behavior

O(1): Flat line
O(log n): Grows slowly and flattens
O(n): Straight diagonal
O(n²): Curved line (steeper)
O(2ⁿ): Grows explosively

8. How to Calculate Time Complexity (Step-by-Step)

Break code into blocks (loops, recursions)
Calculate time for each block
Add or multiply depending on nesting


for (let i = 0; i < n; i++) {
  console.log(i);        // O(1)
}
// Total = O(n * 1) = O(n)

9. Types of Interview/Contest Questions

Category	Example Question	Difficulty
Loop Analysis	Find complexity of nested loops	Easy
Recursion	Fibonacci recursion complexity	Medium
Sorting	Compare Merge and Bubble sort	Medium
Optimization	Reduce TLE using prefix sum	Hard
Space Analysis	Recursive vs iterative space	Medium

10. Practice Examples

🔹 Example 1: Binary Search


function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}
// Time: O(log n), Space: O(1)

🔹 Example 2: Brute Force Subarray Sum


let sum = 0;
for (let i = 0; i < n; i++) {
  for (let j = i; j < n; j++) {
    for (let k = i; k <= j; k++) {
      sum += arr[k];
    }
  }
}
// Time: O(n³) — highly inefficient

🔹 Optimized: Prefix Sum


// Preprocess
let prefix = Array(n+1).fill(0);
for (let i = 0; i < n; i++) {
  prefix[i+1] = prefix[i] + arr[i];
}

// Query sum of [i..j] = prefix[j+1] - prefix[i]