Programmer Humor

19187 readers

1483 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

Keep content in english
No advertisements
Posts must be related to programming or programmer topics

founded 1 year ago

MODERATORS

[email protected]

403

Not everything can be done in constant time, that's O(k) (sh.itjust.works)

submitted 2 months ago by [email protected] to c/[email protected]

41 comments fedilink hide all child comments

you are viewing a single comment's thread
view the rest of the comments

[–] [email protected] 1 points 2 months ago (10 children)

unless the problem space includes all possible functions f , function f must itself have a complexity of at least n to use every number from both lists , else we can ignore some elements of either of the lists , therby lowering the complexity below O(n!²)

if the problem space does include all possible functions f , I feel like it will still be faster complexity wise to find what elements the function is dependant on than to assume it depends on every element , therefore either the problem cannot be solved in O(n!²) or it can be solved quicker

[–] [email protected] 4 points 2 months ago (8 children)

By “certain distance function”, I mean a specific function that forces the problem to be O(n!^2).

But fear not! I have an idea of such function.

So the idea of such function is the hamming distance of a hash (like sha256). The hash is computed iterably by h[n] = hash(concat(h[n - 1], l[n])).

This ensures:

We can save partial results of the hashing, so we don’t need to iterate through the entire lists for each permutation. Otherwise we would get another factor n in time complexity.
The cost of computing the hamming distance is O(1).
Order matters. We can’t cheat and come up with a way to exclude some permutations.

No idea of the practical use of such algorithm. Probably completely useless.

[–] [email protected] 2 points 2 months ago (7 children)

honestly I was very suspicious that you could get away with only calling the hash function once per permutation , but I couldn't think how to prove one way or another.

so I implemented it, first in python for prototyping then in c++ for longer runs... well only half of it, ie iterating over permutations and computing the hash, but not doing anything with it. unfortunately my implementation is O(n²) anyway, unsure if there is a way to optimize it, whatever. code

as of writing I have results for lists of n ∈ 1 .. 13 (13 took 18 minutes, 12 took about 1 minute, cant be bothered to run it for longer) and the number of hashes does not follow n! as your reasoning suggests, but closer to n! ⋅ n.

desmos graph showing three graphs, labeled #hashes, n factorial and n factorial times n

link for the desmos page

anyway with your proposed function it doesn't seem to be possible to achieve O(n!²) complexity

also dont be so negative about your own creation. you could write an entire paper about this problem imho and have a problem with your name on it. though I would rather not have to title a paper "complexity of the magic lobster party problem" so yeah

[–] [email protected] 1 points 2 months ago* (last edited 2 months ago)

actually all of my effort was wasted since calculating the hamming distance between two lists of n hashes has a complexity of O(n) not O(1) agh

I realized this right after walking away from my devices from this to eat something :(

edit : you can calculate the hamming distance one element at a time just after rehashing that element so nevermind

load more comments (6 replies)

load more comments (7 replies)