Which complexity fits which input size

Complexity analysis Mid-level Python 3.13+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

Using a budget of 10⁸ steps, what does this print?

Python 3.13

import math
n = 100_000
budget = 10 ** 8
fits = {"n log n": n * math.log2(n) <= budget,
        "n^2": n * n <= budget}
print(fits)

Options{'n log n': True, 'n^2': False}{'n log n': True, 'n^2': True}{'n log n': False, 'n^2': False}

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A {'n log n': True, 'n^2': False}

Right: about 1.7 million steps fit; 10 billion do not.

Checking the largest input against a rough budget tells you which complexity class to aim for before you code.

Why not the others?

B {'n log n': True, 'n^2': True}. 100,000 squared is 10¹⁰, a hundred times the budget.
C {'n log n': False, 'n^2': False}. n log n is about 1.66 million, well under 10⁸.

For three input sizes, bars show the simple steps each growth class needs, from logarithmic to exponential, next to a one-second rule-of-thumb budget.

Illustrative

Assumption: A rule of thumb for simple steps per second in a compiled language; Python runs fewer.

Text version

n = 20:

n = 20 at 100,000,000 steps per second
Class	Simple steps	Time	Fits 1 s?
O(log n)	4	0 s	Yes
O(n)	20	0 s	Yes
O(n log n)	86	1 µs	Yes
O(n²)	400	4 µs	Yes
O(2ⁿ)	1.05 million	10.5 ms	Yes

n = 100,000:

n = 100,000 at 100,000,000 steps per second
Class	Simple steps	Time	Fits 1 s?
O(log n)	17	0 s	Yes
O(n)	100,000	1 ms	Yes
O(n log n)	1.66 million	16.6 ms	Yes
O(n²)	10 billion	100 s	No, over budget
O(2ⁿ)	too many	–	No, over budget

n = 1,000,000:

n = 1,000,000 at 100,000,000 steps per second
Class	Simple steps	Time	Fits 1 s?
O(log n)	20	0 s	Yes
O(n)	1 million	10 ms	Yes
O(n log n)	19.9 million	0.199 s	Yes
O(n²)	1 trillion	2.78 hours	No, over budget
O(2ⁿ)	too many	–	No, over budget

30-second answer

Use a rough budget of about 10⁸ simple steps per second for compiled code (fewer in Python) and compare it with your complexity at the largest n. For n = 10⁵, O(n²) is 10¹⁰ steps, far over; O(n log n) is about 1.7 million, well under. Tiny limits such as n ≤ 20 hint that exponential search over subsets is expected.

Practise saying it · 45 s. No recording, just a timer

Explain how input limits guide your approach.

Say your answer out loud, then check which of these points you covered:

About 10⁸ simple steps per second
Check the largest n
Small n hints at exponential

Deep dive

The budget is a rule of thumb, not a measurement; the widget below uses it only to compare classes.

Python is often 10 to 100 times slower per simple step than compiled code, so leave more room.

Limits are a hint about the intended solution: interviewers set them with a target in mind.

Common mistakes

Ignoring the limits and coding the first idea.
Treating the rule of thumb as an exact runtime.

Senior take & follow-ups

Mention the limits out loud and the complexity they suggest before choosing an approach.

Follow-up questions

Think of your answer first, then open the hint.

What does n ≤ 10⁹ suggest?
Show hint
O(log n) or O(1): binary search on the answer or a formula.
What about two inputs of 10⁵ each?
Show hint
O(n + m) or O((n + m) log) is fine; O(n·m) is not.

Similar on Android: ANRs: causes and fixes The Android page covers work that blocks the main thread long enough to trigger an ANR; this page estimates how long an algorithm runs for a given input size.

What each operation costs: Bubble Sort · Merge Sort · Binary Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.