Big-O time complexity?

I fear you are misunderstanding "Big-O" notation.

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.

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 Oct 25 '10 at 9:01 1 @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 Oct 25 '10 at 10:05 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 Oct 25 '10 at 10:13 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 Oct 25 '10 at 10:34 @bitmask: Exactly :-). – sleske Oct 25 '10 at 16:05.

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).

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 Oct 25 '10 at 10:01?

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 Oct 25 '10 at 10:08.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.