[Question]
  [
Write a program (or function) that exhibits four common [big O](https://en.wikipedia.org/wiki/Big_O_notation) [time complexities](https://en.wikipedia.org/wiki/Time_complexity) depending on how it is run. In any form it takes in a positive integer N which you may assume is less than 231.
1. When the program is run in its **original** form it should have **[constant](https://en.wikipedia.org/wiki/Time_complexity#Constant_time)** complexity. That is, the complexity should be **Θ(1)** or, equivalently, **Θ(1^N)**.
2. When the program is **reversed** and run it should have **[linear](https://en.wikipedia.org/wiki/Time_complexity#Linear_time)** complexity. That is, the complexity should be **Θ(N)** or, equivalently, **Θ(N^1)**.  
(This makes sense since `N^1` is `1^N` reversed.)
3. When the program is **doubled**, i.e. concatenated to itself, and run it should have **[exponential](https://en.wikipedia.org/wiki/Time_complexity#Exponential_time)** complexity, specifically **2N**. That is, the complexity should be **Θ(2^N)**.  
(This makes sense since the `2` in `2^N` is double the `1` in `1^N`.)
4. When the program is **doubled *and* reversed** and run it should have **[polynomial](https://en.wikipedia.org/wiki/Time_complexity#Polynomial_time)** complexity, specifically **N2**. That is, the complexity should be **Θ(N^2)**.  
(This makes sense since `N^2` is `2^N` reversed.)
These four cases are the only ones you need to handle.
Note that for preciseness I'm using [big theta (Θ) notation](https://stackoverflow.com/q/10376740/3823976) instead of [big O](https://en.wikipedia.org/wiki/Big_O_notation) 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)).
> 
> # Example
> 
> 
> If the original program were
> 
> 
> 
> ```
> ABCDE
> 
> ```
> 
> 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
> 
> 
> 
> ```
> EDCBA
> 
> ```
> 
> 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
> 
> 
> 
> ```
> ABCDEABCDE
> 
> ```
> 
> 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
> 
> 
> 
> ```
> EDCBAEDCBA
> 
> ```
> 
> 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.
> 
> 
> 
# Details
* **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](https://en.wikipedia.org/wiki/Bubble_sort) instead of a faster [sorting algorithm](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Best,_worst_and_average_case), 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\n` reversed is `\r\n` for 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)`.
Remember `O(N^2) != O(N^3)` and `O(2^N) != O(3^N)`.
[Neat big O cheat sheet.](http://bigocheatsheet.com)
# Scoring
This is normal code golf. The shortest original program (the constant time one) in bytes wins.
  
[Answer]
# [Python 3](https://docs.python.org/3/), 102 bytes
```
try:l=eval(input());k=1#)]0[*k**l(tnirp
except:k=2#2=k:tpecxe
print(k**l*[0])#1=k;))(tupni(lave=l:yrt
```
[Try it online!](https://tio.run/nexus/python3#FcoxCoAwDADAvd/oknRSwaWSl4iDlAwloYQSRV9f8eYb3t@sxPepUJtdDoib0BzxmPYkKSl4q90CP4XNs9ASF5LsxuXhYL02h7@lfTowziQbIvhlrYKeN5Pmt3sYY/0A)
This is of O(1^n), since this is what the program does:
* evaluate the input
* create the array [0]
* print it
---
Reversed:
```
try:l=eval(input());k=1#)]0[*l**k(tnirp
except:k=2#2=k:tpecxe
print(l**k*[0])#1=k;))(tupni(lave=l:yrt
```
[Try it online!](https://tio.run/nexus/python3#FcoxCoAwDADAvd/oknRSwaWSl4iDlAwloYQSRV9f8eYbwfublfg@FWqzywFxE5ojHtOeNCUBb7Vb4KeweRZa4kKS3bg8HKzX5vC3tE8HxplkQwS/rFXQ82bS/HYfY/0A)
This is of O(n^1), since this is what the program does:
* evaluate the input
* create the array [0]\*input (0 repeated as many times as the input)
* print it
---
Doubled:
```
try:l=eval(input());k=1#)]0[*k**l(tnirp
except:k=2#2=k:tpecxe
print(k**l*[0])#1=k;))(tupni(lave=l:yrt
try:l=eval(input());k=1#)]0[*k**l(tnirp
except:k=2#2=k:tpecxe
print(k**l*[0])#1=k;))(tupni(lave=l:yrt
```
[Try it online!](https://tio.run/nexus/python3#vc0xCoAwDADAvd/oknRSwaWSl4iDSIaSUEKJoq@v@An3g@venqzE165Qqp0OiIvQGHEb1iQpKXgtzQLfB5tnoSlOJNmNj5uDtVIdPpbWYcM4kiyI4KfVArpfTJqf5uGfpff5BQ)
This is of O(2^n), since this is what the program does:
* evaluate the input
* create the array [0]
* print it
* try to evaluate the input
* fail
* create the array [0]\*(2^input) (0 repeated as many times as 2^input)
* print it
---
Doubled and reversed:
```
try:l=eval(input());k=1#)]0[*l**k(tnirp
except:k=2#2=k:tpecxe
print(l**k*[0])#1=k;))(tupni(lave=l:yrt
try:l=eval(input());k=1#)]0[*l**k(tnirp
except:k=2#2=k:tpecxe
print(l**k*[0])#1=k;))(tupni(lave=l:yrt
```
[Try it online!](https://tio.run/nexus/python3#vc0xCoAwDADAvd/oknRSwaWSl4iDSIaSUEKJoq@v@An3g@vB25OV@NoVSrXTAXERGiNuw5o0JQGvpVng@2DzLDTFiSS78XFzsFaqw8fSOmwYR5IFEfy0WkD3i0nz0/yfpff5BQ)
This is of O(n^2), since this is what the program does:
* evaluate the input
* create the array [0]\*input (0 repeated as many times as the input)
* print it
* try to evaluate the input
* fail
* create the array [0]\*(input^2) (0 repeated as many times as the input squared)
* print it
[Answer]
# Perl 5, ~~82~~ ~~73~~ 71+1 (for -n flag) = 72 bytes
I'm certain I can golf this (a lot) more, but it's bedtime, I've spent enough time debugging as is, and I'm proud of what I have so far anyway.
```
#x$=_$;
$x.=q;#say for(1..2**$_)#)_$..1(rof _$=+x$;;
eval $x;$x=~s/#//;
```
The program itself doesn't use the input, and just evaluates a string beginning with a comment and then does a single string substitution, so this is clearly in constant time. It's basically equivalent to:
```
$x="#";
eval $x;
$x=~s/#//;
```
Doubled:
```
#x$=_$;
$x.=q;#say for(1..2**$_)#)_$..1(rof _$=+x$;;
eval $x;$x=~s/#//;
#x$=_$;
$x.=q;#say for(1..2**$_)#)_$..1(rof _$=+x$;;
eval $x;$x=~s/#//;
```
The bit that actually takes exponential time is the second eval: it evaluates the command `say for(1..2**$_)`, which lists all the numbers from 1 to 2^N, which clearly takes exponential time.
Reversed:
```
;//#/s~=x$;x$ lave
;;$x+=$_ for(1..$_)#)_$**2..1(rof yas#;q=.x$
;$_=$x#
```
This (naively) computes the summation of the input, which clearly takes linear time (since each addition is in constant time). The code that actually gets run is equivalent to:
```
$x+=$_ for(1..$_);
$_=$x;
```
The last line is just so that when these commands are repeated it will take quadratic time.
Reversed and doubled:
```
;//#/s~=x$;x$ lave
;;$x+=$_ for(1..$_)#)_$**2..1(rof yas#;q=.x$
;$_=$x#
;//#/s~=x$;x$ lave
;;$x+=$_ for(1..$_)#)_$**2..1(rof yas#;q=.x$
;$_=$x#
```
This now takes the summation of the summation of the input (and adds it to the summation of the input, but whatever). Since it does order `N^2` additions, this takes quadratic time. It's basically equivalent to:
```
$x=0;
$x+=$_ for(1..$_);
$_=$x;
$x+=$_ for(1..$_);
$_=$x;
```
The second line finds the summation of the input, doing `N` additions, while the fourth does `summation(N)` additions, which is `O(N^2)`.
[Answer]
# [Actually](https://github.com/Mego/Seriously), 20 bytes
```
";(1╖╜ⁿr"ƒ"rⁿ@╜╖1(;"
```
[Try it online!](https://tio.run/nexus/actually#@69krWH4aOq0R1PnPGrcX6R0bJJSEZDhAOJPnWaoYa30/78pAA)
Input: `5`
Output:
```
rⁿ@╜╖1(;
[0]
5
```
---
Reversed:
```
";(1╖╜@ⁿr"ƒ"rⁿ╜╖1(;"
```
[Try it online!](https://tio.run/nexus/actually#@69krWH4aOq0R1PnODxq3F@kdGySUhGQAeQDRQ01rJX@/zcFAA)
Output:
```
rⁿ╜╖1(;
[0, 1, 2, 3, 4]
5
```
---
Doubled:
```
";(1╖╜ⁿr"ƒ"rⁿ@╜╖1(;"";(1╖╜ⁿr"ƒ"rⁿ@╜╖1(;"
```
[Try it online!](https://tio.run/nexus/actually#@69krWH4aOq0R1PnPGrcX6R0bJJSEZDhAOJPnWaoYa1EUMH//6YA)
Output:
```
rⁿ@╜╖1(;
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]
rⁿ@╜╖1(;
rⁿ@╜╖1(;
[0]
```
---
Doubled and reversed:
```
";(1╖╜@ⁿr"ƒ"rⁿ╜╖1(;"";(1╖╜@ⁿr"ƒ"rⁿ╜╖1(;"
```
[Try it online!](https://tio.run/nexus/actually#@69krWH4aOq0R1PnODxq3F@kdGySUhGQAeQDRQ01rJUIKvj/3xQA)
Output:
```
rⁿ╜╖1(;
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]
rⁿ╜╖1(;
rⁿ╜╖1(;
[0, 1, 2, 3, 4]
```
---
## Main idea
Actually is a stack-based language.
* `abc` is a program which has O(1n) complexity, and its double has O(2n) complexity.
* `def` is a program which has O(n1) complexity, and its double has O(n2) complexity.
Then, my submission is `"abc"ƒ"fed"`, where `ƒ` is evaluate. That way, `"fed"` will not be evaluated.
### Generation of individual program
The pseudocode of the first component `;(1╖╜ⁿr`:
```
register += 1 # register is default 0
print(range(register**input))
```
The pseudocode of the second component `;(1╖╜ⁿ@r`:
```
register += 1 # register is default 0
print(range(input**register))
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 20 bytes
Partly inspired by [Leaky Nun's Actually solution](https://codegolf.stackexchange.com/a/118782/53880).
The leading and trailing newlines are significant.
### Normal:
```
⁵Ŀ⁵
R
R²
2*R
‘
⁵Ŀ⁵
```
[Try it online!](https://tio.run/nexus/jelly#@8/1qHHrkf1AgstIK4jrUcMMriCuoEObEML///83BQA)
Input: `5`
Output: 
```
610
```
---
### Reversed:
```
⁵Ŀ⁵
‘
R*2
²R
R
⁵Ŀ⁵
```
[Try it online!](https://tio.run/nexus/jelly#@8/1qHHrkf1AguvQpiCuIK5HDTO4grSMEML///83BQA)
Input: `5`
Output:
```
[1, 2, 3, 4, 5]10
```
---
### Doubled
```
⁵Ŀ⁵
R
R²
2*R
‘
⁵Ŀ⁵
⁵Ŀ⁵
R
R²
2*R
‘
⁵Ŀ⁵
```
[Try it online!](https://tio.run/nexus/jelly#@8/1qHHrkf1AgstIK4jrUcMMriCuoEObEMIEFfz//98UAA)
Input: `5`
Output:
```
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]10
```
---
### Doubled and Reversed
```
⁵Ŀ⁵
‘
R*2
²R
R
⁵Ŀ⁵
⁵Ŀ⁵
‘
R*2
²R
R
⁵Ŀ⁵
```
[Try it online!](https://tio.run/nexus/jelly#@8/1qHHrkf1AguvQpiCuIK5HDTO4grSMEMIEFfz//98UAA)
Input: `5`
Output:
```
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]10
```
---
### Explanation
The key here is in `Ŀ`, which means "calls the link at index n as a monad." The links are indexed top to bottom starting at 1, excluding the main link (the bottom-most one). `Ŀ` is modular as well, so if you try to call link number 7 out of 5 links, you'll actually call link 2.
The link being called in this program is always the one at index 10 (`⁵`) no matter what version of the program it is. However, which link is at index 10 depends on the version.
The `⁵` that appears after each `Ŀ` is there so it doesn't break when reversed. The program will error out at parse-time if there is no number before `Ŀ`. Having a `⁵` after it is an out of place nilad, which just goes straight to the output.
**The original version** calls the link `‘`, which computes n+1.
**The reversed version** calls the link `R`, which generates the range 1 .. n.
**The doubled version** calls the link `2*R`, which computes 2n and generates the range 1 .. 2n.
**The doubled and reversed version** calls the link `²R`, which computes n2 and generates the range 1 .. n2.
[Answer]
# [Befunge-98](http://quadium.net/funge/spec98.html), 50 bytes
## Normal
```
\+]#:\-1vk  !:;#
@k!:-1 .: ;#]#$ <;
[*:>@ 
&$< ^&;
```
This is by far the simplest program of the 4 - the only commands that are executed are the following:
```
\+]
  !
  : @
&$< ^&;
```
This program does some irrevelant stuff before hitting a "turn right" command (`]`) and an arrow. Then it hits **2** "take input" commands. Because there is only 1 number in input and because of how TIO treats `&`s, the program exits after 60 seconds. If there are 2 inputs (and because I can without adding bytes), the IP would travel up into the "end program" function.
[Try it online!](https://tio.run/nexus/befunge-98#@x@jHatsFaNrWJatoKBoZa3M5ZCtaKVrqKBnpWCtHKusomBjzRWtZWXnoMClpmKjEKdm/f@/MQA "Befunge-98 – TIO Nexus")
## Reversed
```
;&^ <$&
 @>:*[
;< $#]#; :. 1-:!k@
#;:!  kv1-\:#]+\
```
This one is a little more complicated. the relevant commands are as follows:
```
;&^  $
  >:*[
;< $#]#; :. 1-:!k@
  :
```
which is equivalent to
```
;&^                   Takes input and sends the IP up. the ; is a no-op
  :                   Duplicates the input.
  >:*[                Duplicates and multiplies, so that the stack is [N, N^2
     $                Drops the top of the stack, so that the top is N
     ]#;              Turns right, into the loop
         :.           Prints, because we have space and it's nice to do
            1-        Subtracts 1 from N
              :!k@    If (N=0), end the program. This is repeated until N=0
;< $#]#;              This bit is skipped on a loop because of the ;s, which comment out things
```
The important part here is the  `:. 1-:!k@` bit. It's useful because as long as we push the correct complexity onto the stack before executing in a lower time complexity, we can get the desired one. This will be used in the remaining 2 programs in this way.
[Try it online!](https://tio.run/nexus/befunge-98#@2@tFqdgo6LGpeBgZ6UVzWVto6CiHKtsrWClp2Coa6WY7cClbG2lqKCQXWaoG2OlHKsd8/@/OQA "Befunge-98 – TIO Nexus")
## Doubled
```
\+]#:\-1vk  !:;#
@k!:-1 .: ;#]#$ <;
[*:>@ 
&$< ^&;\+]#:\-1vk  !:;#
@k!:-1 .: ;#]#$ <;
[*:>@ 
&$< ^&;
```
And the relevant command are:
```
\+]
  !
  :
&$< ^&;\+]#:\-1vk  !:;#
@k!:-1 .: ;#]#$ <;
```
This program goes into 2 loops. First, it follows the same path as the normal program, which pushes 1 and N onto the stack, but instead of wrapping around to the second `&`, the IP jumps over a comment into a loop that pushes `2^N`:
```
        vk!:    If N is 0, go to the next loop.
      -1        Subtract 1 from N
 +  :\          Pulls the 1 up to the top of the stack and doubles it
  ]#            A no-op
\               Pulls N-1 to the top again
```
The other bits on line 4 are skipped using `;`s
After (2^N) is pushed onto the stack, we move down a line into the aforementioned printing loop. Because of the first loop, the time complexity is Θ(N + 2^N), but that reduces to Θ(2^N).
[Try it online!](https://tio.run/nexus/befunge-98#@x@jHatsFaNrWJatoKBoZa3M5ZCtaKVrqKBnpWCtHKusomBjzRWtZWXnoMClpmKjEKdmTbqO//@NAQ "Befunge-98 – TIO Nexus")
## Doubled and Reversed
```
;&^ <$&
 @>:*[
;< $#]#; :. 1-:!k@
#;:!  kv1-\:#]+\;&^ <$&
 @>:*[
;< $#]#; :. 1-:!k@
#;:!  kv1-\:#]+\
```
The relevant commands:
```
;&^
;< $#]#; :. 1-:!k@
 @>:*[
  :
```
This functions almost identically to the reversed program, but the `N^2` is not popped off of the stack, because the first line of the second copy of the program is appended to the last line of the first, meaning that the drop command (`$`) never gets executed, so we go into the printing loop with `N^2` on the top of the stack.
[Try it online!](https://tio.run/nexus/befunge-98#@2@tFqdgo6LGpeBgZ6UVzWVto6CiHKtsrWClp2Coa6WY7cClbG2lqKCQXWaoG2OlHKsdQ7qO//9NAQ "Befunge-98 – TIO Nexus")
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 90 bytes
```
f=n=>n&&f(--n)+f(n);f(t);var t=process.argv[1]//;);--i;]1[vgra.ssecorp:t*t?t=i=t rav(rof"
```
[Try it online!](https://tio.run/##BcExDsIwDADAnVdUDFUCcqsOLESBh1QdrJBUYbAjx8rzMXdfHNiT1KZA/MlmJVJ80TwXB0D@Xhz5UJz6MFAmjU045d4XlHPs27GuwQeAGo5tH6fg0ntOLO2pN31rrFEnweGEy/Vi9uOmlakb2OMP "JavaScript (Node.js) – Try It Online")
Trivial
]