Consider the following two functions. What are time complexities of the functions?int fun1(int n){if (n <= 1) return n;return 2*fun1(n-1);}int fun2(int n){if (n <= 1) return n;return fun2(n-1) + fun2(n-1);}(A) O(2^n) for both fun1() and fun2()(B) O(n) for fun1() and O(2^n) for fun2()(C) O(2^n) for fun1() and O(n) for fun2()(D) O(n) for both fun1() and fun2()

Consider the following two functions. What are time complexities of th

1.	Consider the following two functions. What are time complexities of the functions?int fun1(int n){if (n <= 1) return n;return 2*fun1(n-1);}int fun2(int n){if (n <= 1) return n;return fun2(n-1) + fun2(n-1);}(A) O(2^n) for both fun1() and fun2()(B) O(n) for fun1() and O(2^n) for fun2()(C) O(2^n) for fun1() and O(n) for fun2()(D) O(n) for both fun1() and fun2()
Answer»

Discussion

No Comment Found

Related InterviewSolutions

In the following C function, let n >= m.int gcd(n,m){if (n%m ==0) return m;n = n%m;return gcd(m, n);}How many recursive calls are made by this function?(A) (logn)(B) (n)(C) (loglogn)(D) (sqrt(n))(A) A(B) B(C) C(D) D
Consider the following functions: f(n) = 2^n g(n) = n! h(n) = n^logn Which of the following statements about the asymptotic behavior of f(n), g(n), and h(n) is true?(A) f(n) = O(g(n)); g(n) = O(h(n))(B) f(n) = (g(n)); g(n) = O(h(n))(C) g(n) = O(f(n)); h(n) = O(f(n))(D) h(n) = O(f(n)); g(n) = (f(n))(A) A(B) B(C) C(D) D
What is the time complexity of Floyd–Warshall algorithm to calculate all pair shortest path in a graph with n vertices?(A) O(n^2logn)(B) Theta(n^2logn)(C) Theta(n^4)(D) Theta(n^3)
What does it mean when we say that an algorithm X is asymptotically more efficient than Y?(A) X will be a better choice for all inputs(B) X will be a better choice for all inputs except possibly small inputs(C) X will be a better choice for all inputs except possibly large inputs(D) Y will be a better choice for small inputs
In a competition, four different functions are observed. All the functions use a single for loop and within the for loop, same set of statements are executed. Consider the following for loops:A) for(i = 0; i < n; i++)B) for(i = 0; i < n; i += 2)C) for(i = 1; i < n; i *= 2)D) for(i = n; i > -1; i /= 2)If n is the size of input(positive), which function is most efficient(if the task to be performed is not an issue)?(A) A(B) B(C) C(D) D
What is the time complexity of the below function?void fun(int n, int arr[]){int i = 0, j = 0;for(; i < n; ++i)while(j < n && arr[i] < arr[j])j++;}(A) O(n)(B) O(n^2)(C) O(nlogn)(D) O(n(logn)^2)
Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let n = D1D2…Dmint n, rev;rev = 0;while (n > 0){rev = rev*10 + n%10;n = n/10;}The loop invariant condition at the end of the ith iteration is: (GATE CS 2004)(A) n = D1D2….Dm-i and rev = DmDm-1…Dm-i+1(B) n = Dm-i+1…Dm-1Dm and rev = Dm-1….D2D1(C) n != rev(D) n = D1D2….Dm and rev = DmDm-1…D2D1
Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4? f1(n) = 2^n f2(n) = n^(3/2) f3(n) = nLogn f4(n) = n^(Logn)(A) f3, f2, f4, f1(B) f3, f2, f1, f4(C) f2, f3, f1, f4(D) f2, f3, f4, f1
What is time complexity of fun()?int fun(int n){int count = 0;for (int i = n; i > 0; i /= 2)for (int j = 0; j < i; j++)count += 1;return count;}(A) O(n^2)(B) O(nLogn)(C) O(n)(D) O(nLognLogn)
Which of the following is not O(n^2)?(A) (15^10) * n + 12099(B) n^1.98(C) n^3 / (sqrt(n))(D) (2^20) * n

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment