Asymptotic analysis "o" to "O" conversion
My understanding about "O" and "o" notation is that former is an upper bound and latter is a tight bound. My question is, if a function., f(n) is tight bound by some random function., say o(g(n)). Can this bound be made an upper bound ie,(O(g(n)) by multiplying some constant "c" such that it will be an upper bound even when n->infinity.
f ∈ O(g) says, essentially
For at least one choice of a constant k > 0, you can find a constant a such that the inequality 0 <= f(x) <= kg(x) holds for all x > a.
Note that O(g) is the set of all functions for which this condition holds.
f ∈ o(g) says, essentially
For every choice of a constant k > 0, you can find a constant a such that the inequality 0 <= f(x) < kg(x) holds for all x > a.
Once again, note that o(g) is a set.
From Wikipedia:
Note the difference between the earlier formal definition for the big-O notation, and the present definition of little-o: while the former has to be true for at least one constant M the latter must hold for every positive constant ε, however small. In this way, little-o notation makes a stronger statement than the corresponding big-O notation: every function that is little-o of g is also big-O of g, but not every function that is big-O of g is also little-o of g (for instance g itself is not, unless it is identically zero near ∞).
This link contains good explanation:
http://www.stat.cmu.edu/~cshalizi/uADA/13/lectures/app-b.pdf
上一篇: 如何编写斐波那契数列？
下一篇: 渐近分析“o”到“O”的转换