Compare growth while keeping the cost model explicit
Asymptotic analysis asks how work changes as input grows. Constants and lower-order terms become less important at large sizes, but still influence real performance for bounded workloads.
Consider T(n) = 3n² + 20n + 7. Its quadratic term eventually dominates, so T(n) is Θ(n²). Doubling a sufficiently large input increases work by roughly four, rather than two. For n log₂ n, doubling gives 2n(log₂ n + 1), a little more than twice the work.
fun comparisons(size: Int): Long {
require(size >= 0)
var count = 0L
for (i in 0 until size) {
for (j in i + 1 until size) count++
}
return count
}
The inner loop length changes with i. Total work is n(n-1)/2, not simply an arbitrary “two loops” rule.
Exercise
Evaluate counts for sizes zero through five and match them to the formula. Then compare measured counts at 100 and 200.
Check: state whether arithmetic, hashing, or string comparison is assumed constant-time; a string comparison can itself depend on string length.