# CodeStepByStep

## bigoh4

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

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) int sum = 0; for (int i = 0; i < N; i++) { sum++; } for (int i = 100*N; i >= 0; i--) { sum++; } cout << sum << endl;``` answer: ```// b) int sum = 0; for (int i = 1; i < N - 2; i++) { for (int j = 0; j < N * 3; j += 2) { for (int k = 0; k < 1000; k++) { sum++; } } } cout << sum << endl;``` answer: ```// c) vector v; for (int i = 0; i < N; i++) { v.push_back(i); } while (!v.empty()) { v.erase(v.begin()); } cout << "done!" << endl;``` answer: ```// d) set set; for (int i = 0; i < N/2; i++) { set.insert(i); } stack stack; for (int i = 0; i < N/2; i++) { set.erase(i); stack.push(i); } cout << "done!" << endl;``` answer: ```// e) queue queue; for (int i = 1; i <= N; i++) { queue.push(i * i); } unordered_map map; while (!queue.empty()) { int k = queue.front(); queue.pop(); map[k] = N * N; } cout << "done!" << endl;``` answer: