what is order notation f(n)=O(g(n))?

Posted by Lopa on Stack Overflow See other posts from Stack Overflow or by Lopa
Published on 2010-04-09T16:57:05Z Indexed on 2010/04/09 17:03 UTC
Read the original article Hit count: 370

2 questions:

question 1: under what circumstances would this[O(f(n))=O(k.f(n))] be the most appropriate form of time-complexity analysis?

question 2: working from mathematical definition of O notation, show that O(f(n))=O(k.f(n)), for positive constant k.?

My view: For the first one I think it is average case and worst case form of time-complexity. am i right? and what else do i write in that?

for the second one I think we need to define the function mathematically, so is the answer something like because the multiplication by a constant just corresponds to a readjustment of value of the arbitrary constant 'k' in definition of O.

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about time-complexity