Separate upper, lower, and tight bounds
Big O gives an asymptotic upper bound, Ω a lower bound, and Θ a tight bound. These symbols do not themselves mean worst, best, or average case; first choose the case or cost function, then bound it.
For linear search, a successful match at the first index uses one comparison: best-case Θ(1). An absent target uses n comparisons: worst-case Θ(n). The algorithm uses Θ(1) auxiliary space because only a loop index and fixed-size values are needed; the input array is not newly allocated workspace.
fun sum(values: IntArray): Long {
var total = 0L
for (value in values) total += value
return total
}
This visits every value for all inputs of length n, giving Θ(n) time under a fixed-width arithmetic model. Output storage and input storage should be reported separately when relevant.
Exercise
Analyze a function that copies an array and then scans the copy. Contrast its auxiliary space with the function above. Next analyze a function that returns all n elements as a new list.
Check: explain why saying an algorithm is O(n²) may be technically true but uninformative when a tighter O(n) bound applies.