The work hidden in a call
Include copied parameters, helper bodies, string operations, and input/output in your estimate.
A short expression can do a long scan
sumArray(a, n) may fit on one line but visits n elements. Calling it q times costs O(q(n + 1)); when q = n, the positive-size bound is quadratic. Wrapping a scan in a named helper does not change that work.
If the input and length do not change, compute the sum once and reuse it. Recomputing n sums costs O(n²); one sum plus n additions costs O(n). A demonstration that runs both versions is still dominated by the slow version.
// Complete C++23 program. No input; output: 15
#include <iostream>
long long sumArray(const int a[], int n) {
long long total = 0;
for (int i = 0; i < n; ++i) total += a[i];
return total;
}
int main() {
int a[]{2, -1, 4};
long long sum = sumArray(a, 3);
std::cout << 3 * sum << '\n';
}The parameter can cost more than the body
A helper taking an existing length-L string by value budgets linear copy work and O(L) additional storage before its body can inspect the string. Even if that body only calls empty(), the whole call is not constant-time under this model.
For q sequential calls, those copies can contribute O(qL) work but only O(L) peak extra storage if each copy disappears before the next is created. A const reference removes the parameter copy; it does not remove a scan performed inside the body.
Account for library and whole-program work
String size() and empty() are constant-time. substr creates another string and copies its selected characters. Comparing two strings can scan a long common prefix. std::sort on n integers uses O(n log n) comparisons; long-string comparisons can make each comparison more expensive.
Reading L characters or printing n bounded-size integers also costs work. A helper that reads one already-stored character may be O(1), while the whole program still had to read its entire input. Optimizers can simplify toy counters, so these counting examples are not stopwatch benchmarks.
Growth explorer
Idealized operation counts show growth. Actual runtime also depends on the implementation and machine.
O(1)1O(log n)7O(n)100O(n log n)665O(n²)10,000Bar lengths use a logarithmic scale. Logarithms use base 2.
Guided simulation · Change the inputs to test your understanding.
emptyCopy(std::string text) only returns text.empty(). Called n times with an existing length-n string, what cost must be included?
Turn the idea into code
For q threshold queries on a stored n-element array, a read-only helper scans the whole array and counts values ≥ the threshold. Give total time and helper auxiliary space, including n = 0. Does using a const array parameter eliminate the repeated scans?
Give me a hint
Charge one full scan to each query, plus per-query setup and output.
Show the explained solution
The query batch takes O(q(n + 1)) time and O(1) helper auxiliary space. A const array parameter avoids mutation and does not copy all array elements, but the body still visits n values per query. The stored input itself uses separate storage.
Your notes
Mark complete when you can explain it yourself.