algorithm - Why is only one of the given statements about complexity classes correct? -
apparently correct answer following question (c), why other options not correct until know value of n?
if n=1, of these seem correct except (b)! going wrong?
which of following not o(n2)?
(a) 1510 * n + 12099
(b) n1.98
(c) n3 / √n
(d) 220 * n
wikipedia says :-
big o notation describes limiting behavior of function when argument tends towards particular value or infinity, in terms of simpler functions. description of function in terms of big o notation provides upper bound on growth rate of function.
an upper bound means f(n) = n can expressed o(n), o(n2), o(n3), , others not in other functions o(1), o(log n).
so, going in same direction, can eliminate options shown below :-
1510 * n + 12099 < c * n2, n > √12100 i.e. n > 110 --- hence o(n2).
n1.98 < n2, n > 1 --- , o(n2).
n3 / √n = n5/2 > n2 n > 1 --- hence, isn't o(n2).
220 * n = 1024*1024*n < c* n2 n > 1 ,where c = 1024*1024 --- hence, o(n2).
hence, option doesn't satisfy o(n2) option c,i.e., f(n) = (n^3 / (sqrt(n)))
. here, so, (n3 / (sqrt(n))) isn't equal o(n2).
Comments
Post a Comment