bigoh4X

Language/Type: C++ algorithm analysis big-oh
Author: Marty Stepp (on 11/04)

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 v; for (int i = 1; i <= N; i++) { v.insert(0, 2 * i); } HashSet s; for (int k : v) { s.add(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 q; for (int i = 1; i <= 4 * N; i++) { q.enqueue(i); } Map map; while (!q.isEmpty()) { int k = q.dequeue(); map[k] = -2 * k; } cout << "done!" << endl;``` answer: ```// d) HashMap map; for (int i = 1; i <= N * N; i++) { map.put(i, i * i + 1); } HashSet set; for (int k : map) { set.add(map[k]); } cout << "done!" << endl;``` answer: