Time complexity counts primitive operations as a function of input size. One pass over a vector is O(n); binary search on sorted data is O(log n).
Examples
- Access
v[i]— O(1) - Linear search unsorted data — O(n)
std::sort— O(n log n) typical- Check all pairs — O(n²)
Hidden costs
std::vector::insert in the middle shifts elements—O(n). push_back amortized O(1). Know your container operations.
Binary search steps
#include
#include
int main() {
std::vector a = {2, 5, 8, 12, 16};
int target = 12;
int lo = 0, hi = (int)a.size() - 1, steps = 0;
while (lo <= hi) {
++steps;
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) break;
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
std::cout << "steps=" << steps << " (O(log n))\n";
return 0;
} Important interview questions and answers
- Q: Why mid = lo + (hi-lo)/2?
A: Avoids overflow from (lo+hi)/2 and is standard interview style. - Q: Is sort always O(n log n)?
A: Comparison sorts are; counting sort can be O(n) with constraints on value range.
Self-check
- What is time complexity of linear search?
- What is time complexity of binary search on sorted array?
Pitfall: vector::insert in the middle is O(n)—not O(1) like push_back amortized.
Interview prep
- Binary search time?
O(log n) on sorted data.
- std::sort?
O(n log n) comparison sort typical.