PLEASE EXPLAIN YOUR ANSWERS CLEARLY.

DO NOT POST AN INCOMPLETE / SLOPPY OR WRONG ANSWER PLEASE AS I I WILL NOT UNDERSTAND IT AND WILL REPORT YOU!!

WRONG ANSWERS ALSO BLOCK THE QUESTION FROM GETTING ANSWERED PROPERLY, THANK YOU!

1)What is the time complexity of each of the following functions? Explain your answers.

int f1(int n) { int count = 0;

for (int i = n; i > 0; i /= 2) for (int j = 0; j count += 1;

return count; }

int f2(int n) { int count = 0;

for (int i = 0; i for (int j = i; j > 0; j--) count += 1;

return count; }

void f3(int n, int arr[]) { int i = 0, j = 0;

for (; i while (j j++; }

void f4(int n) { int i, x=0;

for (i = 1; i if (i % 2 == 1) x++; }

2)Order the following functions in increasing order of asymptotic complexity. Explain your answer.

f1(n) = 2^n

f2(n) = n^(3/2)

f3(n) = nlogn

f4(n) = n^(logn)

3)What is the time complexity for each of the following for loops? Explain your answers.

(A) for (int i = 0; i

(B) for (int i = 0; i

(C) for (int i = 1; i

(D) for (int i = n; i > -1; i /= 2)

4)What does it mean when we say that an algorithm X is asymptotically more efficient than Y?

5)Big-O notation is used to classify running-time functions. If f(n) is O(g(n)) then f(n) is within a constant factor of g(n). Definition: Let f(n) and g(n) be two functions on positive integers. We say f(n) is O(g(n)) if there exist two positive constants c and k such that f(n) = k. For each of the following algorithms, show that f(n) is O(g(n)):

f(n) g(n) f(n) = 10n + 5 g(71) = n f(n) = 3n2 +4n + 1 g(n) = n2 n f(n) = 4n3 + 10n2 + 3n-100 g(n) = n3 f(n) = n4 + 7n+ 12 g(71) = n no 541 72 0774 134n