You are using an out of date browser. It may not display this or other websites correctly.
You should upgrade or use an alternative browser.
You should upgrade or use an alternative browser.
Big 'Oh' notation.
- Thread starter Reb
- Start date
SlipEternal
Junior Member
- Joined
- Jan 4, 2012
- Messages
- 114
If for two sequences \(\displaystyle f(n), g(n)\) with \(\displaystyle g(n)\geq 2\) we have \(\displaystyle f(n)=O(g(n))\),
then \(\displaystyle log(f(n))=O(log(g(n)))\).
Does this continue to hold if we allow \(\displaystyle g(n)<2\)?
If \(\displaystyle g(n)<2\), then \(\displaystyle g(n)=1\). But, \(\displaystyle \log(1) = 0\). I don't know much about Big O notation, but I would imagine that it doesn't work well as a function of zero.
SlipEternal
Junior Member
- Joined
- Jan 4, 2012
- Messages
- 114
I don't see anything requiring \(\displaystyle g(n)\in \mathbb{N}\) especially since \(\displaystyle \log g(n)\) wouldn't otherwise be.
As I said, I don't know much about big o notation. Typically, \(\displaystyle g(n)\) is used when the function is \(\displaystyle g:\mathbb{N} \to \)something, and \(\displaystyle g(x)\) is used when the input can be any real number. But, again, I don't know the notation at all.
Notation
My bad. Let f(n)=O(g(n)) iff there exists a C>0 such that
|f(n)|<C|g(n)|, for n large.