Powerprogramming: O(1^N), O(N^1), O(2^N), O(N^2) all in one

66

11

Write a program (or function) that exhibits four common big O time complexities 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 complexity. That is, the complexity should be Θ(1) or, equivalently, Θ(1^N).

  2. 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 N^1 is 1^N reversed.)

  3. 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 in 2^N is double the 1 in 1^N.)

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

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

Scoring

This is normal code golf. The shortest original program (the constant time one) in bytes wins.

Calvin's Hobbies

Posted 2017-05-04T04:14:41.493

Reputation: 84 000

Excellent question! Minor point: we don't have to specify worst-case / best-case / average-case, because the only input that counts as size N is the number N itself (which BTW is not the usual notion of input size: that would treat input N as being of size log N). So there is only one case for each N, which is simultaneously the best, worst, and average case. – ShreevatsaR – 2017-05-05T04:50:10.537

5It appears that you've deviated from the usual definitions of complexity. We always define the time complexity of an algorithm as a function of the size of its input. In the case where the input is a number, the size of the input is the base-2 logarithm of that number. So the program n = input(); for i in xrange(n): pass has exponential complexity, because it takes 2 ** k steps, where k = log_2(n) is the input size. You should clarify whether this is the case, as it dramatically changes the requirements. – wchargin – 2017-05-05T13:10:16.637

Answers

36

Python 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!

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!

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!

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!

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

Leaky Nun

Posted 2017-05-04T04:14:41.493

Reputation: 45 011

Why does it not hang awaiting user interaction when there are multiple calls to input()? – Jonathan Allan – 2017-05-04T06:50:32.133

@JonathanAllan I guess Ctrl+D (end of transmission) is sent to the program from TIO. EDIT: it should be "end of file". – Leaky Nun – 2017-05-04T06:51:24.350

It's certainly not the default, but whether it is a loophole or not is beyond me. – Jonathan Allan – 2017-05-04T06:53:53.820

1It's a loophole that "end of transmission" is transmitted at the end of transmission? – Leaky Nun – 2017-05-04T06:54:33.453

I have no idea, it just seems wrong that a normal run will require more input from the user. Input is not usually part of the program transmission. – Jonathan Allan – 2017-05-04T07:00:23.713

You did that in a mainstream language too! Awesome! Hats off! – Arjun – 2017-05-04T07:35:57.213

@Arjun Thanks for your appreciation. – Leaky Nun – 2017-05-04T07:40:18.347

1Can you explain it? – Brain Guider – 2017-05-04T10:49:32.890

1Re: the "end of file" argument, you're looking at things backwards. When you're using a terminal, requests for input hang because there's something connected to it; ctrl-D can be sent to explicitly send no input. If the input is connected to an empty file (like TIO does if you leave the input box empty), or if it's connected to a file where all the input has been read, there's no need for the request for input to do anything; it already knows there's no input. On UNIX/Linux, "end of file" and "no input available" are indistinguishable on regular files. – None – 2017-05-04T12:50:28.880

A @AnderBiguri asked, can you please explain why your programs have the correct time complexities? From the OP: "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." – Kevin – 2017-05-04T15:56:27.103

@Kevin calm down, I just came back. – Leaky Nun – 2017-05-04T16:02:22.780

3For the first case, k is the input, and l is one, so you're still computing 1**k, right? Which should take O(log(k)) time, despite that fact that you and I and everybody knows in advance that it's one? – Richard Rast – 2017-05-04T17:16:16.647

@RichardRast that is a good point. That would depend on the implementation of power. – Leaky Nun – 2017-05-04T17:16:50.197

18

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

Chris

Posted 2017-05-04T04:14:41.493

Reputation: 1 313

Great! Doing that in a mainstream language would have been tough! This has my upvote! – Arjun – 2017-05-04T07:37:09.740

Well done, this is pretty nice. You probably meant $x.=q;##say... instead of $x.=q;#say... though (with two # instead of 1). (That would explain why you counted 76 bytes instead of 75). Also, you should count -n flag in your bytecount, as your program doesn't do much without it. – Dada – 2017-05-04T11:53:30.933

@Dada I accidentally transposed the eval and the s/// commands. If you do the eval first you only need the one #. Good catch! – Chris – 2017-05-04T15:56:00.183

@Chris Right, it works indeed. You might be able to omit the last #: $x=~s/#//; reversed produces ;//#/s~=x$, which in your context does nothing, as it would with a leading #. (I haven't test it though). Regardless, have a +1 ! – Dada – 2017-05-04T15:59:34.933

@Dada Nice catch once again! – Chris – 2017-05-04T16:08:54.107

17

Actually, 20 bytes

";(1╖╜ⁿr"ƒ"rⁿ@╜╖1(;"

Try it online!

Input: 5

Output:

rⁿ@╜╖1(;
[0]
5

Reversed:

";(1╖╜@ⁿr"ƒ"rⁿ╜╖1(;"

Try it online!

Output:

rⁿ╜╖1(;
[0, 1, 2, 3, 4]
5

Doubled:

";(1╖╜ⁿr"ƒ"rⁿ@╜╖1(;"";(1╖╜ⁿr"ƒ"rⁿ@╜╖1(;"

Try it online!

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!

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

Leaky Nun

Posted 2017-05-04T04:14:41.493

Reputation: 45 011

I never thought this will be even possible! Great work, sir! +1 – Arjun – 2017-05-04T07:28:16.127

@Arjun Thank you for your appreciation. – Leaky Nun – 2017-05-04T07:28:44.160

This is excellent and truly rises to the challenge by not using comments IMO. Awesome! – ShreevatsaR – 2017-05-05T05:47:09.413

1Well this actually has comments... the strings are unevaluated and are NOPs... – Leaky Nun – 2017-05-05T05:48:14.130

4

Jelly, 20 bytes

Partly inspired by Leaky Nun's Actually solution.

The leading and trailing newlines are significant.

Normal:


⁵Ŀ⁵
R
R²
2*R
‘
⁵Ŀ⁵

Try it online!

Input: 5

Output: 

610

Reversed:


⁵Ŀ⁵
‘
R*2
²R
R
⁵Ŀ⁵

Try it online!

Input: 5

Output:

[1, 2, 3, 4, 5]10

Doubled


⁵Ŀ⁵
R
R²
2*R
‘
⁵Ŀ⁵

⁵Ŀ⁵
R
R²
2*R
‘
⁵Ŀ⁵

Try it online!

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!

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.

Business Cat

Posted 2017-05-04T04:14:41.493

Reputation: 8 927

4

Befunge-98, 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!

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!

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!

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!

MildlyMilquetoast

Posted 2017-05-04T04:14:41.493

Reputation: 2 907

Asked: 2017-05-04T04:14:41.493

Viewed: 4 971 times

Active: 2017-05-05T01:39:38.463