3 ms·
Note that calling it 2^O(N) (or Omega) would be more accurate, unless you stumbled upon a really lucky coincidence.
by atq2119 6y ago
Note that calling it 2^O(N) (or Omega) would be more accurate, unless you stumbled upon a really lucky coincidence.
- titanomachy 6y agoAre there any functions f(n) ∈ O(n) such that 2^(f(n)) ∉ O(2^(n))? If not, then either statement is accurate.
- gnramires 6y agoYes, for example 2^(2n) ∉ O(2^(n)). Any function of a different linear coefficient. Big-O notation represents a bound by a constant factor (by modifying the exponent multiplier you get an exponential factor).
- titanomachy 6y agoThanks, you're right of course.
- MaxBarraclough 6y agoInteresting, I'd never seen this kind of thing. Related: https://en.wikipedia.org/wiki/Big_O_notation#Multiple_uses https://en.wikipedia.org/wiki/Big_O_notation#Multiple_uses