How to use the Time Complexity Calculator
- 1. Choose a modeNested loops, or a recurrence of the form T(n) = a·T(n/b) + n^d.
- 2. Describe itPick each loop's type, or type a, b and d.
- 3. Read the resultSee the Big-O, the C code it stands for, and a table comparing exact counts with the growth function.
Worked example: loops
The default has an outer loop over n, an inner loop that runs i times, and a halving loop inside that. Multiplying gives n(n−1)/2 × (log₂ n + 1), so the complexity is O(n² log n). For n = 16 the innermost line runs exactly 600 times (120 × 5), against a growth function of 16² × 4 = 1,024, a ratio of 0.586. At n = 65,536 the ratio is 0.531. It stays in a narrow band, which is what Big-O promises: the constant ½ and the +1 don't change the growth.
Worked example: master theorem
Merge sort makes 2 recursive calls on halves and does linear work to merge, so a = 2, b = 2 and d = 1. Since log₂ 2 = 1 = d, it's case 2 and T(n) = Θ(n log n). Karatsuba multiplication (a = 3, b = 2, d = 1) has log₂ 3 ≈ 1.585 > 1, so the leaves dominate and T(n) = Θ(n^1.585). Binary search (a = 1, b = 2, d = 0) gives Θ(log n).
Rules of thumb
- Nested loops multiply; loops one after another add, and you keep the biggest term.
- A loop that halves or doubles its variable runs about log₂ n times.
- Recurrences like T(n) = T(n−1) + n or T(n) = 2T(n−1) + 1 aren't master-theorem form; they sum to O(n²) and O(2ⁿ).
Frequently asked questions
Are the iteration counts simulated?
They're exact formulas, and the tests confirm them against real nested loops for small n.
Why is a √n loop O(√n) and not O(n)?
It stops when i × i passes n, so it runs about √n times.
Does it read my code?
No. You describe the loops; it doesn't parse code.
Is the time complexity calculator free?
Yes. Everything in the time complexity calculator works without signing up. The first time you ask for a result, we ask once for your name and WhatsApp number; after that the time complexity calculator and every other Uncodemy tool open straight away.