In Big- notation, analyze the running time of the following pieces of code/pseudo-code. Describe the running time as a function of the input size (here, n). You should always explain your work when solving mathematics problems.

Part (a) void f1(int n) int t = sqrt(n); for(int i = 0; i > f2(int n) std::map > t1; std::vector v1; for(int i=1; i > x; std::map >:: iterator it; it = t1.find( x ); if( it == t1.end()){ int k = 1 + (x % n); while(k >= 1) { t1[k].push_back(x); k /= 2; else { v1.push_back(x); return t1; Part (d) Notice that this code is somewhat similar to what happens if you keep inserting into a vector. int *a = new int [10]; // new is 0(1) int size = 10; for (int i = 0; i > f2(int n) std::map > t1; std::vector v1; for(int i=1; i > x; std::map >:: iterator it; it = t1.find( x ); if( it == t1.end()){ int k = 1 + (x % n); while(k >= 1) { t1[k].push_back(x); k /= 2; else { v1.push_back(x); return t1; Part (d) Notice that this code is somewhat similar to what happens if you keep inserting into a vector. int *a = new int [10]; // new is 0(1) int size = 10; for (int i = 0; i