000000000000000000
+5
A:
I fear you are misunderstanding "Big-O" notation.
A notation is not "expressed" as an algorithm. Rather, the Big-O notation describes a property of an algorithm.
So it's not "O(N) can be expressed as XXX", but rather "algorithm XXX has complexity of O(N)".
That said, it is quite reasonable to ask for examples of algorithms with a certain complexity; you already list some. To address your questions:
O(4^n) is the same as O(e^n), often written as O(exp(n)) (try to understand why it is the same). O(4^n) belongs to the class of algorithms with "exponential complexity" (EXPTIME). Many important problems in math/CS have exponential complexity (or nearly exponential complexity).
An algorithm with exponential complexity would be for example a naive solution to the discrete logarithm problem.
For the other complexities I cannot give an example, but you will probably find one by googling a bit.
sleske
2010-10-25 08:35:28
I don't buy your O(a^n) = O(b^n) with a,b>1. While it is true that the basis is irrelevant when dealing with logarithms, this does not hold for exponential functions. Otherwise the entire EXPTIME class would be a set of problems with O(2^n) (or more conveniently O((1+epsilon)^n)) algorithms.
bitmask
2010-10-25 09:01:00
@bitmask: Actually, it is. Wikipedia e.g. defines EXPTIME as "the set of all decision problems solvable by a deterministic Turing machine in O(2^p(n)) time" (with p(n) being a polynomial in n).
sleske
2010-10-25 10:05:32
BTW, my original statement "O(4^n) is the same as O(e^n)" is of course false. What I had in mind (but very dimly) was that they are both in EXPTIME. Thanks for reminding me :-).
sleske
2010-10-25 10:13:15
Yes, that is something different. O(2^p(n)) CONTAINS all O(a^n), as you can hide the different base (a) inside p. For instance, if p(n)=2n, then you have 2^(p(n)) = 4^n. But that does not imply that O(2^n) = O(4^n).
bitmask
2010-10-25 10:34:38
@bitmask: Exactly :-).
sleske
2010-10-25 16:05:07
A:
The algorithms you have given are strictly speaking not Big-O but Theta. Big-O is an asymptotic upper bound meaning that on some worse case input the running time will be the one given but isn't for all inputs, where as Theta is a tight bound meaning that the running time will always be that. Consider for instance a sorting algorithm that is given an already sorted list as input, or a search algorithm where the things to be found is the first element in a list (how does binarysearch compare to linear search in this case).
Matti
2010-10-25 08:45:09
@Matti - If we are going to be nit-picky. Any algorithm that is `Theta(f(N))` is *also* `O(f(N))`. So the OP is actually correct in saying they are Big-O
Stephen C
2010-10-25 10:01:55
??? Those are all both Big-O **and** Omega, implying Theta. "meaning that on some worse case input". Theta is just being more specific, the lower bound has been found/proven as well. It is not related to worst case. "running time will always be that" is strictly speaking not correct, better would be "the growth of rate is proportional with Theta".
Ishtar
2010-10-25 10:08:15