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 <[email protected]>wrote: > 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 <[email protected]>wrote: > >> *Let w(n) and A(n) denote respectively, the worst case and average case >> running time of an algorithm executed on an input of size n. which of the >> following is ALWAYS TRUE?* >> (A) [image: A(n) = \Omega(W(n))] >> (B) [image: A(n) = \Theta(W(n))] >> (C) [image: A(n) = O(W(n))] >> (D) [image: A(n) = o(W(n))] >> >> answer is c >> >> plz explain y??? >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
