0

Consider a Function f(n) and g(n),now my question is that is it possible that f(n) is a member of bigOh(g(n)) as well as a member of smalloh(g(n)). I am confused because of this question's solution http://clrs.skanev.com/03/problems/02.html how can A be small oh as well as big oh both of B? please help

sourav_anand
  • 551

2 Answers2

2

Anything that is $o(g(n))$ is also $O(g(n))$. Just look at the definitions.

$f(n) = O(g(n))$ means that there are some positive numbers $N$ and $K$ such that $|f(n)| \le K |g(n)|$ for all $n \ge N$. $f(n) = o(g(n))$ means there is a positive number $N$ such that for every positive number $K$, $|f(n)| \le K |g(n)|$. If it's true for every $K$, then it is true for at least one $K$ (e.g. $K=1$).

Robert Israel
  • 448,999
1

Big-O implies that for f ∈ O(g), the f's asymptotic growth is no faster than g's. f ∈ o(g) means that f's asymptotic growth is strictly slower than g's. In a way it is like <= and <. Therefore, anything that is is a member of small-o, o(g(n)) is also a member of Big-O, O(g(n)).