5 ms·

Programming languages have native support for O(n) algorithms in the form of for loops. You can compose as many of those as you want to get a huge polynomial, b

Programming languages have native support for O(n) algorithms in the form of for loops. You can compose as many of those as you want to get a huge polynomial, but you have to go out of your way and do something a bit weird to get an exponential run time.

kortilla 7y ago
What? It’s trivial to go exponential. for i in n: for j in n: whoops(i, j)
- esotericn 7y ago
  That's n^2.
- reggieband 7y ago
  That is polynomial time (specifically quadratic). See this stack overflow on polynomial vs. exponential: https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time https://stackoverflow.com/questions/4317414/polynomial-time-...
  - justincredible 7y ago
    whoops is O(2^n)
- _wldu 7y ago
  Two for loops, one nested under the other, both upto N is clearly O(N^2) in the worst case. Three for loops (in the same manner) is O(N^3).
- a1369209993 7y ago
  Actually, that should be: whoops(n): for i in n: whoops(n-1) Your version is merely quadratic.
  - trehalose 7y ago
    I don't quite understand your code, but if I'm guessing correctly that n is an integer and "for i in n" means in human terms "for all non-negative integers less than n", that is not exponential, that is actually factorial, which is superexponential. Uh, or close to factorial, I'm not sure exactly. Testing it in python right now, incrementing a counter each time whoops is called, I'm seeing a relationship that looks like whoops(n) == n * whoops(n-1) + 1 That is interesting.
    - a1369209993 7y ago
      > that is not exponential, that is actually factorial, which is superexponential Fair point; I should have given: whoops(n): if(!n) return for i in 2: whoops(n-1) I think it's clear that it is "trivial to go exponential", though. And for that matter, also trivial to go superexponential apparently.
saagarjha 7y ago
Recursion is a pretty good way to exponential quickly.

kortilla 7y ago

What? It’s trivial to go exponential. for i in n: for j in n: whoops(i, j)

esotericn 7y ago
That's n^2.
reggieband 7y ago
That is polynomial time (specifically quadratic). See this stack overflow on polynomial vs. exponential: https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time https://stackoverflow.com/questions/4317414/polynomial-time-...
- justincredible 7y ago
  whoops is O(2^n)
_wldu 7y ago
Two for loops, one nested under the other, both upto N is clearly O(N^2) in the worst case. Three for loops (in the same manner) is O(N^3).
a1369209993 7y ago
Actually, that should be: whoops(n): for i in n: whoops(n-1) Your version is merely quadratic.
- trehalose 7y ago
  I don't quite understand your code, but if I'm guessing correctly that n is an integer and "for i in n" means in human terms "for all non-negative integers less than n", that is not exponential, that is actually factorial, which is superexponential. Uh, or close to factorial, I'm not sure exactly. Testing it in python right now, incrementing a counter each time whoops is called, I'm seeing a relationship that looks like whoops(n) == n * whoops(n-1) + 1 That is interesting.
  - a1369209993 7y ago
    > that is not exponential, that is actually factorial, which is superexponential Fair point; I should have given: whoops(n): if(!n) return for i in 2: whoops(n-1) I think it's clear that it is "trivial to go exponential", though. And for that matter, also trivial to go superexponential apparently.

saagarjha 7y ago

Recursion is a pretty good way to exponential quickly.