Complexity (a) What is the complexity of the following function, f? You must ful

Question

Complexity

(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) {
result = g(N);
} else {
for (i=0; i < N; i++) {
result = result + g(result);
}
}
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.

Explanation / Answer

a) In the first function either it goes into if or else.. in if its O(n)-->given in else the loop runs n times so->O(n), therfore O(n) or O(n)===> O(n);

b) For a max size array n, it eliminates half of its size until 1 element is remaining means according to sizes, 1,2,,4,8,....,n/4,n/2,n, therefore 2x=n ==> x=logn

c) yes , since y=2x+3 be eq 1 with time complexity O(n) and y=x2+4x+3 be eq 2 with time complexity O(n2).. As we know that eq 1 can be solved easily and faster than compared to eq 2.. we say O(n) is faster than O(n2).

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.