O(n^2), again, now in Windows Management Instrumentation

Re:O(n^2), again, now in Windows Management Instrumentation by a1369209993 on Monday December 09, 2019 @09:19PM (#21749013)

Actually, that should be:

  whoops(n):
    for i in n:
      whoops(n-1)

Your version is merely quadratic.

[ Parent | on HN ]

Re:O(n^2), again, now in Windows Management Instrumentation by trehalose on Tuesday December 10, 2019 @12:08AM (#21749769)

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.

[ Parent | on HN ]

Re:O(n^2), again, now in Windows Management Instrumentation by a1369209993 on Tuesday December 10, 2019 @06:20PM (#21757916)

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

[ Parent | on HN ]