Log n

2 snippets in Interview Prep

Also written as n log n

DSAInterview Prep

O(n log n) — Linearithmic Time

syntax

Typical of efficient comparison-based sorts. You divide (log n levels) and do O(n) work per level.

example

// JavaScript
// Merge sort achieves O(n log n) guaranteed
const sorted = [5, 2, 8, 1, 9].sort((a, b) => a - b);
// Built-in sort: V8 uses TimSort → O(n log n)

# Python
# Python's sorted() uses TimSort → O(n log n)
result = sorted([5, 2, 8, 1, 9])
# list.sort() is in-place, also O(n log n)

output

Time: O(n log n) | Space: O(n) for merge sort, O(log n) for quicksort avg

Note O(n log n) is the theoretical lower bound for comparison-based sorting. If an interviewer asks you to do better, the input must have special structure (e.g., bounded integers for counting sort). Heap operations on n elements also yield O(n log n).

Binary Search on Sorted Array

DSA · Arrays & Strings

syntax

lo = 0, hi = length - 1
while lo <= hi:
  mid = lo + (hi - lo) // 2
  compare and adjust lo or hi

example

// JavaScript
function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1; // not found
}

# Python
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

output

binary_search([1,3,5,7,9,11], 7) → 3

Note Time O(log n), Space O(1). Off-by-one errors are the #1 bug — practice until the template is muscle memory. Use lo <= hi when searching for exact match. Use lo < hi when narrowing to a single candidate. Always test with 0, 1, and 2 element arrays.