SyntaxShelf

O(log n)

2 snippets in Interview Prep

Also written as O(n log n)

DSAInterview Prep

O(log n) - Logarithmic Time

DSA · Big-O Notation
Syntax
Each step halves the remaining work. Classic sign: dividing the problem space in two.
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;
    else if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

# 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
Time: O(log n) | Space: O(1)

Note Balanced BST operations are O(log n). Use mid = lo + (hi - lo) // 2 instead of (lo + hi) // 2 to prevent integer overflow. If you see 'sorted array' in a problem, think binary search immediately.

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).

Frequently asked questions

How does Interview Prep handle O(log n)?
Interview Prep covers this with 2 copy-ready snippets on this page. The "O(log n) - Logarithmic Time" snippet in Interview Prep uses `Each step halves the remaining work. Classic sign: dividing the problem space in two.`.
Which code does the Interview Prep example use?
The "O(log n) - Logarithmic Time" snippet uses `Each step halves the remaining work. Classic sign: dividing the problem space in two.`, from the Big-O Notation section of the Interview Prep cheat sheet.
What other Interview Prep snippets are shown for "O(log n)"?
Besides "O(log n) - Logarithmic Time", this page also shows "O(n log n) - Linearithmic Time".
Is there anything to watch out for?
Yes. For "O(log n) - Logarithmic Time": Balanced BST operations are O(log n). Use mid = lo + (hi - lo) // 2 instead of (lo + hi) // 2 to prevent integer overflow. If you see 'sorted array' in a problem, think binary search immediately.

Browse all tasks by intent