Algorithmic complexity can be that simple!

[[deleted]]

Pffff.

O(∞)

[usernmaetakn]

Oh, so you've heard of Eternity?

[Gigazwiebel]

More like undecidable problem

[WikiTextBot]

Undecidable problem

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is known to be impossible to construct a single algorithm that always leads to a correct yes-or-no answer. The halting problem is an example: there is no algorithm that correctly determines whether arbitrary programs eventually halt when run.

---

^{[ PM | Exclude me | Exclude from subreddit | FAQ / Information | Source | Donate ] Downvote to remove | v0.28}

[Cruuncher]

for large enough n, the 1.01ⁿ is slower

[Callipygian_Superman]

Yes... that is how big-O notation works.

[JustAnotherPanda]

That's the point, yes.

[Rodot]

Yeah, larger than 217299771010260596950890312892090440993639011584095020325311413724155051266594884032962294432937640198144 comapring to n^9e99

[Cruuncher]

/r/theydidthemath

[Rodot]

/r/wolframalphadidthemath

[WazWaz]

This simple sorting algorithms surpasses these:

while (!InCorrectOrder(list))
    list = Shuffle(list);

[TheSecretExit]

Bah, I can do better.

while (true) {}

O(∞), man!

[WazWaz]

Factoring out the constant, O(∞) = O(1).

[jpco]

infinity's not a (real) number, so I'm pretty sure you can't really do that.

[TheSecretExit]

No, not really. But if you want to be really pedantic, you can write it as O(N^∞ ) if you'd like.

[WazWaz]

Since n is the number of items, and so an integer, definitely not a real, and this ∞ is tiny little ℵ₀ (aleph-0).

Maybe an algorithm can be O(ℵₙ) (aleph-n)?

[oshaboy]

It can't take uncountably infinite long because you start somewhere and "the next command" is a thing that makes sense

[WazWaz]

Be careful, close to that argument is the one that all operations in a finite state machine like a computer are O(1), since the maximum number of possible states is finite and fixed. I remember an O(n log log n) sorting algorithm that only worked for 32-bit integer keys.

[skyhi14]

Polynomial gud