SyntaxShelf

Log n

2 snippets in Interview Prep

Also written as n log n

DSAInterview Prep

O(n log n) - Linearithmic Time

DSA · Big-O Notation
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.

Frequently asked questions

How do you log n?
Interview Prep covers this with 2 copy-ready snippets on this page. The "O(n log n) - Linearithmic Time" snippet in Interview Prep uses `Typical of efficient comparison-based sorts. You divide (log n levels) and do O(n) work...`.
Which code does the Interview Prep example use?
The "O(n log n) - Linearithmic Time" snippet uses `Typical of efficient comparison-based sorts. You divide (log n levels) and do O(n) work...`, from the Big-O Notation section of the Interview Prep cheat sheet.
What other Interview Prep snippets are shown for "log n"?
Besides "O(n log n) - Linearithmic Time", this page also shows "Binary Search on Sorted Array".
Is there anything to watch out for?
Yes. For "O(n log n) - Linearithmic Time": 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).

Browse all tasks by intent