logo CodeStepByStep logo

Main Page → Exercises → C++ → Solve an Exercise

bigoh19sp

Language/Type: C++ algorithm analysis big-oh
Related Links:
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?
What is the runtime of countDistinct2?
What is the runtime of countDistinct3, if mysterySort is insertion sort?
What is the runtime of countDistinct3, if mysterySort is merge sort?

You must log in before you can solve this problem.

Log In

Need help?

Stuck on an exercise? Contact your TA or instructor.

If something seems wrong with our site, please

Is there a problem? Contact us.