algorithmsbig ocomplexitycomputer science
Consider the formal definition:
f(n) = O(g(n))
Why is it not:
f(n) = O(f(n))
or
f(n) = O(c*f(n))
since for the Big O analysis, f(n)=2n and g(n)=n are identical?
I am confused by the function f(n) using another function.
Why isn' t the definition as follows:
f(n) <= c*abs(g(n))
What does the formal O(g(x)) add to the definition? It seems like it overcomplicates things.
In short: a smaller(bigger) exponent of n.
It relates directly to a part of my answer to an earlier question of yours here:
, which basically says that n to some power grows faster, if the exponent is bigger, regardless of constant factors.
In case 1, function f(n) is assumed to be polynomially smaller than this one:
Don't get scared by the logarithm here, it is just a number, because a and b are constants, so is log_b(a). (Which is why poly-logarithmically does not enter the picture, in that case)
It is then defined to what class of functions f(n) must belong to. This is already the answer to your question "what it means to be polynomially smaller":
All it means is, that the exponent of n must be less than log_b(a): You subtract a positive number (epsilon) from it.
This is another way of looking at it:
The polynomially bigger one has more factors of n: epsilon more. (or less in the case of smaller)
At 57:30 he gives an example, where he ends up in case 1: He compares f(n) = n with n^2. f(n) is polynomially smaller because 1 < 2.
When calculating the Big-O complexity of an algorithm, the thing being shown is the factor that gives the largest contribution to the increase in execution time if the number of elements that you run the algorithm over increases.
If you have an algorithm with a complexity of (n^2 + n)/2 and you double the number of elements, then the constant 2 does not affect the increase in the execution time, the term n causes a doubling in the execution time and the term n^2 causes a four-fold increase in execution time.
As the n^2 term has the largest contribution, the Big-O complexity is O(n^2).
Best Answer
This is an extremely weird definition and is actually new to me. The symbols, as defined by Bachmann and Landau, are not defined like that.
Unfortunately, the German wikipedia is the only source, I can find exactly this, as of now, but I suppose you can see without much translation, that
is defined as 
.
, which I suppose basically states the same, although I think it is incorrect, given that f(n) is something completely different than f).
(Please note: the french wikipedia has the following similar definition
As I explained in response to a different question, O means "the order of", and thus O(g) is actually the set of all functions, that have the same order as g. It makes only sense to say:
So for the sake of nitpicking (which is the fun part in formalization), one can say the definition you criticize is indeed wrong.