---

⭐ What Is Big-O Notation?

Big-O notation is a mathematical way of describing how fast an algorithm grows as the input size increases.

It doesn’t measure:

• CPU time
• Memory
• Performance on your laptop

Instead, it measures:

• Scalability
• Growth rate
• Worst-case behavior

Think of Big-O as a performance label for algorithms.

---

⭐ Why Do We Use Big-O?

Because actual execution time changes based on:

• System performance
• Browser/Node version
• CPU/GPU speed
• Compiler optimization
• Input data
• Available memory

But growth rate never lies.

Big-O shows us which algorithm will still be fast even for 1M or 10M inputs.

---

⭐ The Purpose of Big-O

Big-O answers the question:

👉 “How does the running time grow when input size (n) grows?”

---

⭐ Important Rules of Big-O

1️⃣ We always focus on worst-case

E.g., searching an element in an array: Best-case = first element Worst-case = last element or not found We use worst-case: O(n).

2️⃣ Constants Don’t Matter

O(2n) → O(n) O(5n + 100) → O(n)

We only care about growth trend, not exact numbers.

3️⃣ Drop Lower Order Terms

O(n² + n) → O(n²) O(n + log n) → O(n) (if n dominates)

---

⭐ Most Common Big-O Complexities (Ranked Best → Worst)

Big-O	Name	Example
O(1)	Constant	Accessing array by index, Hash map lookup
O(log n)	Logarithmic	Binary search
O(n)	Linear	Loop through array
O(n log n)	Linearithmic	Sorting (Merge sort, QuickSort avg case)
O(n²)	Quadratic	Nested loops
O(2ⁿ)	Exponential	Recursion that branches (Fibonacci naive)
O(n!)	Factorial	Permutations (traveling salesman brute force)

---

⭐ Now Let’s Explain Each of Them in Depth

---

🔥 1. O(1) — Constant Time

The speed does not depend on the size of input.

Example:

let x = arr[2];       // Always constant time

Even if arr has:

• 10 items
• 10,000 items
• 10,000,000 items

…access by index is always one step.

---

🔥 2. O(n) — Linear Time

Work increases in proportion to input size.

Example:

for (let i = 0; i < arr.length; i++) {
  console.log(arr[i]);
}

If arr has:

• 10 items → 10 steps
• 100 items → 100 steps
• 1,000 items → 1,000 steps

Growth is straight line.

---

🔥 3. O(n²) — Quadratic Time

Nested loops are the most common cause.

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    console.log(i, j);
  }
}

If n doubles:

• Work becomes 4x

If input increases to 1,000:

• Steps = 1,000,000

This is slow for large inputs.

---

🔥 4. O(log n) — Logarithmic Time

Each step halves the input size.

Perfect example: Binary Search

function binarySearch(arr, target) {
  let low = 0, high = arr.length - 1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);

    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

If n = 1,024 Log₂(1024) = 10 steps

This is extremely fast.

---

🔥 5. O(n log n) — Linearithmic

Used in efficient sorting algorithms:

• MergeSort
• HeapSort
• QuickSort (average)

These algorithms divide the array (log n) and then process each element (n).

So: divide × process → n log n

---

🔥 6. O(2ⁿ) — Exponential Time

Brute-force recursion where each call creates 2 calls.

Example: Fibonacci (naive version)

function fib(n) {
  if (n <= 1) return n;
  return fib(n-1) + fib(n-2);
}

If n = 10 → 1024 calls If n = 50 → 1 trillion+ calls 😨

Always avoid unless input size is tiny.

---

🔥 7. O(n!) — Factorial Time

Worst possible case. Used in solving permutations, like:

• Traveling Salesman
• Generating all possible seat arrangements
• Generating permutations

Example:

function permute(arr) {
  if (arr.length === 0) return [[]];

  let result = [];
  for (let i = 0; i < arr.length; i++) {
    let rest = [...arr.slice(0, i), ...arr.slice(i+1)];
    for (let p of permute(rest)) {
      result.push([arr[i], ...p]);
    }
  }
  return result;
}

Too slow for anything above n = 10.

---

⭐ Big-O Space Complexity

Space complexity measures extra memory used.

Examples:

let a = 10;  // O(1) space

let arr = []; // O(n) space if arr grows

Recursion also consumes stack space:

function recursion(n) {
  if (n === 0) return;
  recursion(n-1);
}

Space = O(n) (stack frames)

---

⭐ Big-O in Real JavaScript Interview Problems

Example 1: Checking duplicates (Brute force)

for (let i = 0; i < n; i++) {
  for (let j = i+1; j < n; j++) {
    if (arr[i] === arr[j]) return true;
  }
}

Time: O(n²) Space: O(1)

---

Example 2: Using a Set (Optimized)

let set = new Set();
for (let x of arr) {
  if (set.has(x)) return true;
  set.add(x);
}

Time: O(n) Space: O(n) Faster and cleaner.

---

⭐ Big-O Graphically (Intuition)

Growth speed (slow → fast):

O(1) O(log n) O(n) O(n log n) O(n²) O(2ⁿ) O(n!)

The gap between O(n²) and O(2ⁿ)/O(n!) is huge.

---

⭐ Summary (Easy To Remember)

Big-O	Meaning	Example
O(1)	Constant	Hash lookup
O(log n)	Super fast	Binary search
O(n)	Linear	Loop
O(n log n)	Sorting	MergeSort
O(n²)	Quadratic	Nested loops
O(2ⁿ)	Exponential	Recursive Fibonacci
O(n!)	Factorial	Permutations

---

⭐ What Is Space Complexity?

Space Complexity measures how much extra memory an algorithm uses as the input size grows.

This includes:

1. Input space (memory taken by input itself)

2. Auxiliary space (extra memory used by algorithm)

   • variables
   • data structures (arrays, objects, maps, sets)
   • recursion stack
   • temporary buffers

When interviewers say Space Complexity, they mean Auxiliary Space.

---

⭐ Why Space Complexity Matters?

Two algorithms might have the same time complexity but use different amounts of memory.

Example:

• Using an additional array → O(n) space
• Using two pointers (no extra array) → O(1) space

When input size becomes large, memory can also crash the program.

Space complexity helps us answer:

👉 “How much extra memory does the algorithm consume?”

---

⭐ How Do We Calculate Space Complexity?

We count extra space, not input size.

Examples:

let x = 10;  // O(1)
let y = 20;  // O(1)

Even if we have 100 variables:

let a, b, c, d ... ;

Still O(1) because constant space doesn’t scale with input.

But:

let arr = [];  
for (let i = 0; i < n; i++) {
  arr.push(i);
}

Here:

• array grows with input So memory = O(n)

---

⭐ Common Space Complexities

Complexity	Meaning	Example
O(1)	Constant	Two pointers, in-place sorting, variables
O(log n)	Logarithmic	Recursion depth in binary search
O(n)	Linear	New array, Set, Map, queue, recursion stack
O(n log n)	Merge Sort recursion tree + temp array
O(n²)	2D matrix algorithms
O(n!)	Storing all permutations

---

⭐ Let's Explain Each With Deep Understanding

🔥 1. O(1) Space — Constant

The algorithm uses the same amount of memory regardless of input size.

Example:

function sum(arr) {
  let total = 0;   // O(1)
  for (let i = 0; i < arr.length; i++) {
    total += arr[i];
  }
  return total;    // Output stored in 1 variable
}

Even though we loop through arr, we don’t create new memory that grows with input → O(1).

Real-world O(1) examples:

• Two pointer techniques
• Swapping in place
• Updating constant number of variables
• In-place array reversal
• In-place sorting (like selection sort)

---

🔥 2. O(n) Space — Linear

Space grows directly with the size of the input.

Example:

function getCopy(arr) {
  let copy = [...arr]; // creates a new array of size n
  return copy;         // O(n)
}

Because:

• If arr has 10 items → new array has 10
• If arr has 1,000 items → new array has 1,000

More examples of O(n) space:

• Creating a copy of data
• Storing values in Set or Map
• Using recursion that goes n-levels deep
• BFS/DFS storing visited nodes

---

🔥 3. O(log n) Space — Logarithmic

Mostly comes from recursion depth.

Example: Binary Search

function binarySearch(arr, target, left = 0, right = arr.length-1) {
  if (left > right) return -1;

  let mid = Math.floor((left + right) / 2);

  if (arr[mid] === target) return mid;

  if (arr[mid] < target)
    return binarySearch(arr, target, mid + 1, right);   // call stack level +1

  return binarySearch(arr, target, left, mid - 1);
}

Recursion depth = log₂(n) So auxiliary space = O(log n)

---

🔥 4. O(n log n) Space

Example: Merge Sort

Merge Sort needs:

• recursion depth = log n
• temp arrays = n

So total = n log n, but usually simplified to O(n) for auxiliary space.

---

🔥 5. O(n²) Space

Happens when we need 2D data structures.

Example: Creating adjacency matrix:

let matrix = new Array(n).fill(0).map(() => new Array(n).fill(0));

This matrix stores n × n entries → O(n²)

Another example:

• DP table in dynamic programming
• Storing all pairs combinations

---

🔥 6. O(n!) Space

This occurs when storing all permutations:

function permute(nums) {
  if (nums.length === 0) return [[]];

  let result = [];
  for (let i = 0; i < nums.length; i++) {
    let rest = [...nums.slice(0, i), ...nums.slice(i+1)];
    for (let p of permute(rest)) {
      result.push([nums[i], ...p]);   // storing ALL permutations
    }
  }
  return result; // O(n!)
}

Because permutations of n elements = n!

---

⭐ Space Complexity in Recursion

Every recursive call adds a new frame to call stack.

Example:

function countdown(n) {
  if (n === 0) return;
  countdown(n-1);
}

Total calls = n Space = O(n)

Example: Fibonacci (recursive)

function fib(n) {
  if (n <= 1) return n;
  return fib(n-1) + fib(n-2);
}

Depth = n Space = O(n) Time = O(2ⁿ)

---

⭐ Why Time and Space Complexity Are Different

Example:

reverse() in place:

function reverse(arr) {
  let left = 0, right = arr.length - 1;

  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }
}

Time = O(n) Space = O(1) (in-place)

---

Creating a copy to reverse:

function reverseCopy(arr) {
  let result = [];
  for (let i = arr.length - 1; i >= 0; i--) {
    result.push(arr[i]);
  }
  return result;
}

Time = O(n) Space = O(n) (new array)

---

⭐ Summary Table (Easy to Understand)

Space Complexity	Meaning	Example
O(1)	constant memory	variables, two pointers, swapping
O(log n)	recursion stack	binary search
O(n)	linear growth	new array, Set, Map, recursion depth
O(n log n)	divide+store	merge sort
O(n²)	matrix storage	DP table, adjacency matrix
O(n!)	all permutations	backtracking

---

This is one of those topics where most people memorize a few tricks and move on. That’s a mistake. If we actually understand bitwise operations deeply, they become a huge advantage in DSA and performance-heavy code.

Let’s build this properly from the ground up.

---

🧠 1. What are Bitwise Operations?

👉 Bitwise operations work on the binary (bit-level) representation of numbers.

In JavaScript:

• All numbers are 64-bit floating point (IEEE 754)
• BUT bitwise operations convert them into 32-bit signed integers

So internally:

5 → 00000000 00000000 00000000 00000101

---

⚠️ Important Rule (Most people miss this)

👉 Bitwise ops in JS:

• Convert number → 32-bit signed integer
• Perform operation
• Convert back to JS number

This is why:

console.log(5.9 | 0); // 5

---

🔢 2. Binary Basics (Quick)

Decimal	Binary
1	0001
2	0010
3	0011
4	0100
5	0101

---

🔧 3. All Bitwise Operators (Core)

---

✅ 1. AND (&)

👉 Returns 1 only if BOTH bits are 1

5 & 3

101
011
---
001 → 1

📌 Use cases:

• Check specific bits
• Remove bits
• Power of 2 trick

---

✅ 2. OR (|)

👉 Returns 1 if ANY bit is 1

5 | 3

101
011
---
111 → 7

📌 Use cases:

• Set bits
• Merge flags

---

✅ 3. XOR (^)

👉 Returns 1 if bits are DIFFERENT

5 ^ 3

101
011
---
110 → 6

📌 Powerful properties:

a ^ a = 0
a ^ 0 = a

📌 Use cases:

• Find unique element in array
• Swap values (rarely used now)

---

✅ 4. NOT (~)

👉 Flips all bits

~5

Internally:

00000000 00000000 00000000 00000101  (5)
11111111 11111111 11111111 11111010  (~5)

Result:

~5 = -6

👉 Rule:

~n = -(n + 1)

---

✅ 5. Left Shift (<<)

👉 Shifts bits left (adds zeros on right)

5 << 1  // 10

101 → 1010

📌 Equivalent:

n << k = n * (2^k)

---

✅ 6. Right Shift (>>)

👉 Preserves sign (keeps negative sign)

5 >> 1 // 2

101 → 10

📌 Equivalent:

n >> k = Math.floor(n / (2^k))

---

✅ 7. Unsigned Right Shift (>>>)

👉 Fills left with zeros (no sign)

-5 >>> 1

👉 Converts negative → large positive number

---

⚡ 4. Most Important Patterns (DSA Gold)

---

🔥 1. Check if number is EVEN

num & 1 === 0

---

🔥 2. Check Power of 2

num > 0 && (num & (num - 1)) === 0

---

🔥 3. Remove lowest set bit

num & (num - 1)

---

🔥 4. Get lowest set bit

num & -num

---

🔥 5. Count set bits (optimized)

while (n) {
  n = n & (n - 1);
  count++;
}

---

🔥 6. Swap without temp (not recommended in real code)

a = a ^ b;
b = a ^ b;
a = a ^ b;

---

⚠️ 5. Negative Numbers (2’s Complement)

JavaScript uses 2’s complement.

Example:

-5

Steps:

1. 5 → 00000101
2. Flip → 11111010
3. Add 1 → 11111011

---

⚠️ 6. Common Pitfalls (You MUST know)

---

❌ 1. NaN and floats

5.7 & 1 // treated as 5

👉 Always converted to integer

---

❌ 2. Large numbers overflow

Only 32 bits used

---

❌ 3. ~indexOf trick (old JS hack)

if (~arr.indexOf(x)) { }

👉 Avoid this in modern code (confusing)

---

🚀 7. Real-World Use Cases

• Permissions systems (flags)
• Compression algorithms
• Cryptography basics
• Game engines
• Competitive programming

---

🧠 8. Mental Model (This is what we remember)

• Numbers = bits

• Operations = patterns on bits

• Most tricks come from:

  • n & (n - 1)
  • n & -n
  • XOR properties

---

📊 Complexity

All bitwise operations:

👉 Time Complexity: O(1) 👉 Space Complexity: O(1)

---