logo CodeStepByStep logo

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

bigoh4X

Language/Type: C++ algorithm analysis big-oh
Related Links:

Give a tight bound of the nearest runtime complexity class for each of the following code fragments in Big-Oh notation, in terms of the variable N. In other words, write the code's growth rate as N grows. Write a simple expression that gives only a power of N using a caret ^ character for exponentiation, such as O(N^2) to represent O(N2) or O(log N) to represent O(log2 N). Do not write an exact calculation of the runtime such as O(2N3 + 4N + 14). 

// a)
vector<int> v;
for (int i = 1; i <= N; i++) {
    v.insert(v.begin(), 2 * i);
}
unordered_set<int> s;
for (int k : v) {
    s.insert(k);
}
cout << "done!" << endl;
answer: 
// b)
int sum = 0;
for (int i = 1; i <= 100000; i++) {
    for (int j = 1; j <= i; j++) {
        for (int k = 1; k <= N; k++) {
            sum++;
        }
    }
}
for (int x = 1; x <= N; x += 2) {
    sum++;
}
cout << sum << endl;
answer: 
// c)
queue<int> q;
for (int i = 1; i <= 4 * N; i++) {
    q.push(i);
}

map<int, int> map;
while (!q.empty()) {
    int k = q.front();
    q.pop();
    map[k] = -2 * k;
}
cout << "done!" << endl;
answer: 
// d)
unordered_map<int, int> map;
for (int i = 1; i <= N * N; i++) {
    map[i] = i * i + 1;
}
unordered_set<int> set;
for (auto kv : map) {
    set.insert(vk.second);
}
cout << "done!" << endl;
answer:

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.