# CodeStepByStep

## bigoh7

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 = 1; i <= N - 999; i++) { for (int j = 1; j <= 0.0001 * N/2; j++) { sum++; } }``` answer: ```// b) int sum = 0; for (int i = 1; i <= 1000000; i++) { sum++; } int x = 999999; for (int i = 1; i <= x; i++) { for (int j = 1; j <= 999; j++) { sum++; } for (int k = 1; k <= 999; k++) { sum++; } } cout << sum << endl;``` answer: ```// c) vector vecC; for (int i = 1; i <= N; i++) { vecC.insert(vecC.begin(), i); } set setC; for (int i = 0; i < vecC.size(); i++) { setC.insert(vecC[i]); } cout << "done!" << endl;``` answer: ```// d) map mapD; for (int i = 1; i <= N; i++) { mapD[i] = i/2; } set setD; for (int i = 1; i <= N; i++) { int value = mapD[i]; setD.insert(value); mapD.erase(i); } cout << "done!" << endl;``` answer: ```// e) vector vecE; for (int i = 1; i <= N; i++) { vecE.push_back(i); } stack stackE; while (!vecE.empty()) { stackE.push(vecE[vecE.size() - 1]); vecE.erase(vecE.begin() + vecE.size() - 1); } cout << "done!" << endl;``` answer: