Micro-questions over the growth and asymptotics module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.


A. Why growth rate

1. Method A takes 2.5s on a gaming laptop, Method B takes 5.0s on a cheap server. Is A the better algorithm?

Answer

Not necessarily. Runtime in seconds depends on hardware speed, language overhead and CPU load — none of which are properties of the algorithm.

2. What does computer science measure instead?

Answer

How the workload grows as input size scales to infinity.

3. At , contrast with .

Answer

takes about 11 days; finishes in 0.2 seconds — on the exact same computer.

4. Why is that comparison the whole argument for the subject?

Answer

Because no hardware upgrade closes an 11-days-to-0.2-seconds gap. Growth rate beats constant factors at scale, always.


B. The three asymptotics

5. What does mean, formally and plainly?

Answer

Formally . Plainly: an upper bound — at worst, work grows no faster than .

6. What does mean?

Answer

— a lower bound. At best, work grows no slower than .

7. What does mean?

Answer

— a tight bound. Work grows exactly like .

8. State the tight bound rule.

Answer

holds if and only if both and hold simultaneously.

9. Is it correct to say bubble sort is ?

Answer

Technically yes — Big-O is an upper bound and . It is just useless. This is why exists: it forbids a loose claim.


C. Cases versus bounds

10. What are best, average and worst case?

Answer

Best: the input needing the minimum operations. Average: expected work over all probable inputs. Worst: the input causing maximum work.

11. What is the relationship between the three cases and the three notations?

Answer

They are independent. , and are mathematical bounds on a function; best/average/worst choose which function you are bounding. You can state a for the best case.

12. Give the search example for best and worst case.

Answer

Searching for an item at index 0 is (best); searching for a missing item is (worst).

13. Why is worst case the production standard?

Answer

Because attackers choose the input. A hash map is average and worst case, and hash-flooding denial of service deliberately triggers the gap.


D. Recurrences

14. Give the merge sort recurrence and solve it by tree.

Answer

. Tree height , work per level , total .

15. Give the binary search recurrence and solve it.

Answer

. Height , work per level , total .

16. What is the structural difference between those two?

Answer

Merge sort recurses into both halves; binary search discards one. Same height, completely different total.


E. Amortised analysis

17. What does amortised analysis measure?

Answer

The average cost per operation across a guaranteed sequence of operations, where rare expensive steps are paid for by many cheap ones.

18. Walk through the dynamic array append example.

Answer

Normal push ; resize push . Because capacity doubles, appending items totals copies, so

19. How does amortised differ from average case?

Answer

Average case is a statement about the distribution of inputs; amortised is a guarantee about a sequence regardless of input. Amortised does not assume anything is random.


F. Reading constraints

20. Give the constraint → complexity table.

Answer
AllowedFamily
12permutations, backtracking
25subsets, bitmask DP
500Floyd–Warshall, triple loops
10,000quadratic sorts, double loops
1,000,000 / merge sort, hash maps, two pointers
/ binary search, math, bitwise

21. What is this table actually for?

Answer

Reading the intended solution off the constraints before you start — in interviews and competitive programming, is a near-explicit instruction to enumerate subsets.


G. Space complexity

22. Distinguish total space from auxiliary space.

Answer

Total includes the input arrays. Auxiliary is the extra temporary memory the algorithm allocates, excluding the input.

23. What is an in-place algorithm?

Answer

One with auxiliary space — it modifies data directly inside the input array.

24. What is the hidden call stack trap?

Answer

Recursive functions consume auxiliary memory proportional to recursion depth . A recursive function that allocates nothing still takes space.

25. Is a recursive in-order traversal in-place?

Answer

No — it uses call stack, which is balanced and degenerate. Only an iterative Morris traversal is genuinely .


H. Traps

26. Simplify .

Answer

— completely dominates for large inputs.

27. An algorithm processes an array of length and a string of length . What is the complexity?

Answer

— not . Different variables must stay different.

28. When does an algorithm beat an one?

Answer

At small inputs — around , insertion sort beats quicksort on constant overhead. This is why real sort implementations switch to insertion sort for small subarrays.

29. Summarise the module in one sentence.

Answer

Measure growth rather than seconds, bound it above (), below () or tightly (), design against the worst case, and read the constraints to know which family is expected.


Scorecard

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Complexity Analysis