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

Question

Two questions:

Question 1: Under what circumstances would 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, how to 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?

Answer 1

Question 1 is a little vague, but your answer for question 2 is definitely lacking. The question says "working from the mathematical definition of O notation". This means that your instructor wants you to use the mathematical definition:

f(x) = O(g(x)) if and only if limit [x -> a+] |f(x)/g(x)| < infinity, for some a

And he wants you to plug in g(x) = k f(x) and prove that that inequality holds.

The general argument you posted might get you partial credit, but it is reasoning rather than mathematics, and the question is asking for mathematics.

Answer 2

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?

No! Big O notation has NOTHING to do with average case or worst case. It is only about the order of growth of a function - particularly, how quickly a function grows relative to another one. A function f can be O(n) in the average case and O(n^2) in the worst case - this just means the function behaves differently depending on its inputs, and so the two cases must be accounted for separately.

Regarding question 2, it is obvious to me from the wording of the question that you need to start with the mathematical definition of Big O. For completeness's sake, it is:

Formal Definition: f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.

(source http://www.itl.nist.gov/div897/sqg/dads/HTML/bigOnotation.html)

So, you need to work from this definition and write a mathematical proof showing that f(n) = O(k(n)). Start by substituting O(g(n)) with O(k*f(n)) in the definition above; the rest should be quite easy.