8,331 views

2 Answers

Best answer
8 votes
8 votes

Big O notation is used to give the maximum upper bound for running time.This means that the algorithm will not take time greater than the binding function. Let's analyze each of these 

A)  (15^10) * n + 12099   In this polynomial we can safely ignore the constant part 12099, this leaves us with (15^10)*n. Now here too we can ignore (15^10) because it also a constant. This gives us a bound of Theta(n).This Theta (n) will always be bound by O(n^2).

B) n^1.8 will also always be bound by O(n^2).

C) n^3/(sqrt(n))= n^3/ n^0.5= n^2.5, You can clearly see that n^2.5 cannot be bound by n^2. This will increase much faster than n^2. Hence this cannot be O(n^2).

D) (2^20)*n, Similar to the first case this is linear in input as well. Hence it will also be bound by O(n^2).

I hope you've understood the approach.

selected by
Answer:

Related questions

1 votes
1 votes
2 answers
2
Pranav Madhani asked May 26, 2017
1,870 views
int f(int n) { static int i = 1; if (n ≥ 5) return n; n = n + i; i++; return f(n); }The value returned by f(1) is:(a) 5 (b) 6(c) 7 (d) 8 need solution with explaination...
1 votes
1 votes
2 answers
4
Pranav Madhani asked May 25, 2017
4,812 views
Consider the following 2 functions:f(n)= n3, if 0 ≤ n < 10,000= n2, otherwiseg(n)= n, if 0 ≤ n < 100= n2 + 5n, otherwise Which of the following option is correct?(a) ...