What is the time complexity of exponential search?

Best case O(1). Average case O(log i). Worst case O(log n). Space complexity is O(1).

Exponential search

medium

Built for unbounded or unknown-length input - an infinite stream, or an API you can only probe by index. Costs O(log i) where i is where the target actually is.

Best O(1)Average O(log i)Worst O(log n)Space O(1)

Loading the exponential search engine…

Where to go next

Binary search

easy

Halve the search space with every comparison.

Jump search

easy

Skip in blocks of √n, then scan backwards.

Lower and upper bound

medium

The half-open variant that handles duplicates.