Time Complexity

Count how the number of basic steps grows with input size $n$.

Easy

A single loop is $O(n)$ ; two nested loops $O(n^2)$ ; halving each step $O(\log n)$ . Rough guide for 1 second: $n \le 10^8$ for $O(n)$ , $10^6$ for $O(n\log n)$ , $10^4$ for $O(n^2)$ .

Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.

Discussion (0)