Because you can always find a positive constant c for which following
inequality hold true.
A(n) = cW(n) i.e. the avg. case time complexity always upper bounded by
worst case time complexity. Which is the definition of Big O.
On Sat, Aug 25, 2012 at 7:11 PM, rahul sharma
You have to discard option d because , according to definition of small o
notation if f(n) =o(g(n)) then for ALL constants c 0 you have f(n)
cg(n). or Lim(n-infinite) f(n)/g(n) = 0.
On Sat, Aug 25, 2012 at 10:24 PM, vishal yadav vishalyada...@gmail.comwrote:
Because you can always find