Back to questionsWhat is the worst-case time complexity of
JuniorTheoryVery common
What is the worst-case time complexity of has_duplicate for a vector of n elements?
#include <vector>
bool has_duplicate(const std::vector<int>& v) {
for (std::size_t i = 0; i < v.size(); ++i) {
for (std::size_t j = i + 1; j < v.size(); ++j) {
if (v[i] == v[j]) {
return true;
}
}
}
return false;
}O(n²)
- Expecting
O(n): the loops are nested, not one after another, so their step counts multiply instead of adding up. - Expecting
O(n log n)because the inner loop shrinks: it still runs n(n−1)/2 times in total, and dropping the constant 1/2 leavesO(n²).
- How can a
std::setbringhas_duplicatedown to O(n log n)? - How much extra memory does
has_duplicateuse, as a function of n?
