When the program is run in its original form it should have constant complexity. That is, the complexity should be Θ(1) or, equivalently, Θ(1^N).
When the program is reversed and run it should have linear complexity. That is, the complexity should be Θ(N) or, equivalently, Θ(N^1).
(This makes sense since
When the program is doubled, i.e. concatenated to itself, and run it should have exponential complexity, specifically 2N. That is, the complexity should be Θ(2^N).
(This makes sense since the
2^Nis double the
When the program is doubled and reversed and run it should have polynomial complexity, specifically N2. That is, the complexity should be Θ(N^2).
(This makes sense since
These four cases are the only ones you need to handle.
Note that for preciseness I'm using big theta (Θ) notation instead of big O because the runtimes of your programs must be bounded both above and below by the required complexities. Otherwise just writing a function in O(1) would satisfy all four points. It is not too important to understand the nuance here. Mainly, if your program is doing k*f(N) operations for some constant k then it is likely in Θ(f(N)).
If the original program were
then running it should take constant time. That is, whether the input N is 1 or 2147483647 (231-1) or any value in between, it should terminate in roughly the same amount of time.
The reversed version of the program
should take linear time in terms of N. That is, the time it takes to terminate should be roughly proportional to N. So N = 1 takes the least time and N = 2147483647 takes the most.
The doubled version of the program
should take two-to-the-N time in terms of N. That is, the time it takes to terminate should be roughly proportional to 2N. So if N = 1 terminates in about a second, N = 60 would take longer than the age of the universe to terminate. (No, you don't have to test it.)
The doubled and reversed version of the program
should take squared time in terms of N. That is, the time it takes to terminate should be roughly proportional to N*N. So if N = 1 terminates in about a second, N = 60 would take about an hour to terminate.
You need to show or argue that your programs are running in the complexities you say they are. Giving some timing data is a good idea but also try to explain why theoretically the complexity is correct.
It's fine if in practice the times your programs take are not perfectly representative of their complexity (or even deterministic). e.g. input N+1 might sometimes run faster than N.
The environment you're running your programs in does matter. You can make basic assumptions about how popular languages never intentionally waste time in algorithms but, for example, if you know your particular version of Java implements bubble sort instead of a faster sorting algorithm, then you should take that into account if you do any sorting.
For all complexities here assume we are talking about worst-case scenarios, not best-case or average-case.
The space complexity of the programs does not matter, only the time complexity.
The programs may output anything. It only matters that they take in positive integer N and have the correct time complexities.
Comments and multiline programs are allowed. (You may assume
\r\nfor Windows compatibility.)
Big O Reminders
From fastest to slowest it's
O(1), O(N), O(N^2), O(2^N) (order 1, 2, 4, 3 above).
Slower terms always dominate, e.g.
O(2^N + N^2 + N) = O(2^N).
O(k*f(N)) = O(f(N)) for constant k. So
O(2) = O(30) = O(1) and
O(2*N) = O(0.1*N) = O(N).
O(N^2) != O(N^3) and
O(2^N) != O(3^N).
This is normal code golf. The shortest original program (the constant time one) in bytes wins.