this post was submitted on 08 Nov 2024
750 points (98.2% liked)

Programmer Humor

19623 readers
4 users here now

Welcome to Programmer Humor!

This is a place where you can post jokes, memes, humor, etc. related to programming!

For sharing awful code theres also Programming Horror.

Rules

founded 1 year ago
MODERATORS
Feyter@programming.dev
anzo@programming.dev
BurningTurtle@programming.dev
pylapp@programming.dev
750
Not my problem sort (infosec.pub)
submitted 2 weeks ago by 0x4E4F@infosec.pub to c/programmer_humor@programming.dev
71 comments fedilink hide all child comments
 
you are viewing a single comment's thread
view the rest of the comments
[–] 1boiledpotato@sh.itjust.works 8 points 2 weeks ago (1 children)

And the time complexity is only O(1)

[–] voldage@lemmy.world 14 points 2 weeks ago (1 children)

I don't think you can check if array of n elements is sorted in O(1), if you skip the check though and just assume it is sorted now (have faith), then the time would be constant, depending on how long you're willing to wait until the miracle happens. As long as MTM (Mean Time to Miracle) is constant, the faithfull miracle sort has O(1) time complexity, even if MTM is infinite. Faithless miracle sort has at best the complexity of the algorithm that checks if the array is sorted.

Technically you can to down to O(0) if you assume all array are always sorted.

[–] 1boiledpotato@sh.itjust.works 1 points 2 weeks ago

Oh yeah, I didn't think about the time that it takes to check if it's sorted. The sorting time is constant though