Project Euler Forum

zwuupeape wrote:...what? How so? This program is O(1) by definition since its execution time is independent of input (it has no input) and it obviously halts.

Okay, I admit I wasn't quite awake when I made my first reply to this.

zwuupeape wrote:It's true that it will take longer, but it will also take longer if you have a slower computer... Running time is measured relative to input. The running time of this algorithm is indeed O(|logx|) but O(|logx|) = O(1). Actually I don't even understand what's O(logx) supposed to mean. O(logn) means that the running time of the algorithm takes twice as long to halt if the input is raised to the power of 2. if 12 is the solution and it has 2 digits then what is O(2) supposed to mean?

However, for a programme without input, time complexity isn't defined, so strictly speaking it doesn't make sense to say it is O(whatever).
But we can regard it as a programme taking some input n and ignoring it. By definition, its time complexity is O(f) if there is some finite constant C > 0 so that running-time(n) [le] C*f(n). Now the running time is constant, so for all positive constants c, its time complexity is O(c), in particular we may choose c = 2 or c = log |x| (if |x| > 1).

Although, I suspect that Stijn rather read it as an algorithm problem-number → solution, at least that's how I interpreted it.
Nevertheless, due to the limited width of the answer box, it's still constant time.

It's a different algorithm for each problem because each problem has a different solution. The algorithm problem number -> solution needs an array that maps each problem number to its solution so its O(n) space when n is the number of problems and the running time is the time needed to calculate a[n] when array is given.