Python Logarithmic Time O(log n)

O(log n) means logarithmic time: every step cuts the remaining work in half. Because halving shrinks numbers so fast, doubling the input adds only one extra step.

16 elements need 4 halvings, 32 elements need 5, a million elements about 20, a billion about 30. That is why logarithmic algorithms feel instant even on huge data.

The classic example is binary search — but it only works on sorted data. Halving needs an order to know which half to throw away.

The simplest way to see O(log n) is a loop that divides n by 2 until it reaches 1. The number of rounds is the logarithm of n: for n = 16 the loop runs 4 times, because 2 · 2 · 2 · 2 = 16.

16 becomes 8, 4, 2, 1 — four steps. Doubling n to 32 would add just one more step. The // operator is whole-number division, so n stays an int.

Binary search finds a value in a sorted list by always checking the middle element. If the middle is too small, the whole left half is thrown away; if too big, the right half. Each check halves the search range.

Two markers, lo and hi, hold the current range. The loop ends when the value is found or the range is empty.

Python also ships this ready-made: bisect.bisect_left() from the standard library returns the index where the value belongs in the sorted list. When the value is missing, that index is the position where it would be inserted.

In a sorted list of 16 numbers, the search for 13 needs only 4 checks: the range shrinks 16 → 8 → 4 → 2 and lands on index 6. A linear search would have needed 7 steps here — and up to 16.

bisect.bisect_left() finds 9 at index 4, and comparing nums[i] with the value confirms the hit. The missing value 10 gives index 5 — the place where 10 would fit to keep the list sorted — and the comparison prints False.

O(n log n) sits between linear and quadratic and is the complexity of good sorting algorithms: the data is halved again and again (log n levels), and each level does a linear amount of work (n).

In Python you rarely write a sort yourself — nums.sort() orders a list in place, and sorted(nums) returns a new sorted list; both are O(n log n). Sorting once, then binary-searching many times, is a common and fast pattern.

nums.sort() orders the 8 numbers in about 8 · log 8 = 24 steps — far fewer than the 64 a quadratic sort would use, and the gap widens fast as the list grows.