Register

Sample question for practise doubt

6,025 views
2 2 votes
Consider the following 2 functions:
f(n)= n3, if 0 ≤ n < 10,000
= n2, otherwise
g(n)= n, if 0 ≤ n < 100
= n2 + 5n, otherwise

 

Which of the following option is correct?
(a) f(n) is O(n3) (b) g(n) is O(n3)
(c) O(f(n)) is same as O(g(n)) (d) g(n) is O(1)

2 Answers

0 0 votes
At asymptotical(tend to infinite values) ,let here be for n beyond 10000,(as it is the max number in ques) ,

f(n) = n2 = O(n2)  and g(n) = n2+5n = O(n2)

and n2 can be written as O(n3) hence both opt A and B are correct , still opt C wins the race as it is the EXACT answer as both fn and gn are same in Big-oh.
Voting & Accepting an answer helps improve the community
Answer:
← Previous · Silly window syndrom...Next → · Counting
← Previous in category · Based on GATE2005-IT...Next in category → · Gate Sample Practise
Position:
Show:

Related questions

0 0 votes
2 answers 2 answers
9.6k
9.6k views
Pranav Madhani asked May 25, 2017
9,631 views
Gate Sample Practise
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
0 0 votes
1 1 answer
736
736 views
Pranav Madhani asked May 26, 2017
736 views
Gate Sample Practise Questions
#include<stdio.h int f(int *a, int n) { if(n ≤ 0) return 0; else if(*a % 2 = = 0) return *a + f(a+1, n-1); else return *a - f(a+1, n-1); } int main() { int a[] = {12, 7, ...
0 0 votes
0 0 answers
516
516 views
James_Gosling asked Apr 24, 2023
516 views
(x+k)^m=O(x^m) is true or false for x and k being constants?