(a) What is the complexity of the following function, f? You must fully justify your answer....

Transcribed Image Text:

(a) What is the complexity of the following function, f? You must fully justify your answer. You may assume that the function g has a complexity of O(n). int f(int N) { int result, i=0; if (N <= 0) { g (N); result = } else { for (i=0; i < N; i++) { result result + g(result); %3! return result; (b) Give a brief explanation why the complexity of Binary Search is O(log(N)). * (c) Consider the following statement: "A function with a complexity of O(n) will always be faster then one with complexity O(n2)". Is this statement true or false? Clearly explain your answer. (a) What is the complexity of the following function, f? You must fully justify your answer. You may assume that the function g has a complexity of O(n). int f(int N) { int result, i=0; if (N <= 0) { g (N); result = } else { for (i=0; i < N; i++) { result result + g(result); %3! return result; (b) Give a brief explanation why the complexity of Binary Search is O(log(N)). * (c) Consider the following statement: "A function with a complexity of O(n) will always be faster then one with complexity O(n2)". Is this statement true or false? Clearly explain your answer.

Answer rating: 100% (QA)

a int fint N int resulti0 1 ifN 1 Step 1 result g N N Step 2 else fori0iN1 Step 3 re... View the full answer