# CodeStepByStep

## bigoh19sp

Language/Type: C++ algorithm analysis big-oh
Author: Julie Zelenski (on 2019/05/16)

Consider the following three ways to count the number of distinct integers in an unsorted `vector`:

```int countDistinct1(vector<int>& v) {
int numDistinct = 0;
for (int i = 0; i < v.size(); i++) {
bool isDistinct = true;
for (int j = 0; j < i - 1; j++) {
if (v[i] == v[j]) {
isDistinct = false;
}
}
if (isDistinct) {
numDistinct++;
}
}
return numDistinct;
}
```
```int countDistinct2(vector<int>& v) {
set<int> seen;
for (int i = 0; i < v.size(); i++) {
seen.insert(v[i]);
}
return seen.size();
}
```
```int countDistinct3(vector<int>& v) {
mysterySort(v);
int numDistinct = 1;
for (int i = 0; i < v.size() - 1; i++) {
if (v[i] != v[i + 1]) {
numDistinct++;
}
}
return numDistinct;
}
```
 What is the runtime of countDistinct1? O(1) O(log N) O(N) O(N log N) O(N^2) O(N^2 log N) O(N^3) O(2^N) What is the runtime of countDistinct2? O(1) O(log N) O(N) O(N log N) O(N^2) O(N^2 log N) O(N^3) O(2^N) What is the runtime of countDistinct3, if mysterySort is insertion sort? O(1) O(log N) O(N) O(N log N) O(N^2) O(N^2 log N) O(N^3) O(2^N) What is the runtime of countDistinct3, if mysterySort is merge sort? O(1) O(log N) O(N) O(N log N) O(N^2) O(N^2 log N) O(N^3) O(2^N)

You must log in before you can solve this problem.