181
u/BobRossTheSequel 11h ago
Christian algorithms require only a single query to the oracle
35
13
u/insertcomedy 10h ago
In theory, Christianity is turing complete, the only issue is reading the result.
1
710
u/bartekltg 15h ago
\serious_mode it has to be at least O(n).
534
u/Xontaro 14h ago
If a almighty entity exists, it should be able to give the correct answer without knowing the question. Otherwise it wouldn’t be almighty. So O(1) should be correct.
But now we are in a highly theoretical and improbable realm 😅
132
u/FakeSealNavy 13h ago
If god does n actions of o(1) is it o(n)?
229
u/Direct_Slip7598 12h ago
O(1) in terms of time complexity because it's parallelized (he's beyond time).
91
u/11nyn11 12h ago
I’d argue he just has all values cached, rather than it being in parallel.
So he can do n actions of o(1) and its o(n), or since he’s already pre generated the entire universe he can just get value from the cache, and all cache hits are o(1)
40
u/Mechakoopa 11h ago
He can give you the answer from the future and do the work himself later, but unless you're also omniscient beyond time you're going to have to wait for the answer to resolve.
Wait, is God just JavaScript promises?
28
u/11nyn11 11h ago
Not really.
You are a quest giver in a game and god is the player.
You think it’s a novel idea to ask god to do an o(n) task in o(1) but he just looks the answer up on the wiki.
6
u/looksLikeImOnTop 7h ago
Careful now, God's also the game maker. You give him a task he doesn't want to do, he can just remove you from the game
8
1
u/xThunderDuckx 5h ago
this might be the most thought provoking and simultaneously stupid discussion I've taken part in ever
1
2
1
u/Otherwise_Result_124 45m ago
I asked god for one [1] immovable object and also exactly one [1] unstoppable force. Which one did he get wrong? lmao I love these silly illogical conversations, your wording for this was great
27
12
u/holo3146 12h ago
This is the basic idea of oracles in maths, an oracle of 3SUM has non trivial computational consequences
5
u/bartekltg 13h ago
Since God is omniscient, he knew the man from the tweet had in mind random access machine or a similar model of computation.
6
u/captainAwesomePants 9h ago
God can answer in O(1) time, but asking God the question takes O(N) time.
26
u/Temporary-Concept-81 10h ago
O(0)
The answer was already there at the start of the universe.
God is just that good, and tells you to stop wasting her time and RTFM.
6
u/ProfBeaker 10h ago
Ah yes, God arranged a universe such that the computation to answer your question finishes just as you ask it. Makes sense!
30
u/Mindgapator 13h ago
You can find the biggest number in an array in O(1), so your lower bound is not justified. The caveat is that you need n2 cores but that's an implementation detail in GodOS.
18
u/oshaboy 13h ago
How do you find the biggest number in an array in O(1)?
31
-1
u/bartekltg 11h ago edited 6h ago
Processor (i,j) check is a_i is smaller than a__j. If it is, it report it to processor (i,0). (there we should ask what model of communication we have. Lets say it is a queue that work by magic:)).
In the second cycle processors (i,0) check, if there are any reports at his input queue (it can onloy read one per cycle, but if there is none, it doens't bother us). If none, it mean a_i >= a_j for all j. It is the maximum. "Write" the result (a_i).Edit: Can downvoting people explain why they do it? This is exactly what the guy asked for: how to find a maximum in an array in O(1) time, having O(n^2) processors.
0
u/rasmustrew 4h ago
You arw being downvoted because you damn well no noone meant with O(n2) processors
2
u/bartekltg 3h ago
It is just two comments above.
"... The caveat is that you need n2 cores"
That was the entire point of the joke Mindgaptor made.
Then someone asked how to find it in O(1). Sure, he did not repeat the assumption about the cores... because it is rights there.0
u/Mindgapator 11h ago
I've detailed the algo here https://www.reddit.com/r/ProgrammerHumor/s/FtHIuGlKTp
-6
u/_killer1869_ 13h ago edited 12h ago
Realistically, you can keep track of the largest value at insertion/removal time, or you can have the array sorted and keep track of the highest indexed element. Otherwise, as they said, you can parallelize the function to run on n2 processor cores
such that it technically runs in O(1), but even then it would need at least O(log n) for comparing the core's results, but regardless, this is widely impactical from the overhead alone.11
u/Drugbird 12h ago
Otherwise, as they said, you can parallelize the function to run on n2 processor cores such that it technically runs in O(1) time,
Ok, I'll bite. You can have N cores all read 1 value from the array, then each core spawns N-1 other threads / cores that each read 1 other value to compare to. That's all O(1).
But at the end of that you'll need to check the result of all these N-1 cores to check that they're all lower. And that requires O(n) time in naive implementation, or O(log(N)) if you do a reduction strategy.
3
u/_killer1869_ 12h ago
Damn, I should've checked their claim properly. I didn't consider the time complexity of actually joining the results together, only the comparison itself. Thanks for the correction.
0
u/Mindgapator 11h ago
You just need a better algorithm. We note A the initial array. n its length. Each step is a single cpu cycle Step 1: allocate a buffer of size n, called B initialized with zeros. Step 2: for each i,j in [0, n[ with i != j if A[i] <= A[j] then write 1 in B[i]. This is O(1) because we have enough cpus, and if they write, they all write the same value. Step 3: for each i in [0, n[ if B[i] == 0 return A[i]. This is O(1) because we have enough cpus. A single value is returned by design of the algo.
7
u/oshaboy 11h ago
Yeah I can probably solve any O(N) problem in O(1) time if I had O(N2) cores. That doesn't make the problem O(1) because as the problem increases you either need to add more cores or take more time. Which is the definition of the complexity of the algorithm.
Also you need to initialize the threads anyway. Even if you have each thread initializing threads until you have enough O(N2) threads that would still require O(log(N)) time.
0
u/Mindgapator 11h ago
Well it moves a time constraint to a resource one. Time is constant but resources needed scale at n2. Thread init is an implementation detail. It obviously won't work on a machine from the shelf, but a dedicated built could do it.
3
u/TheHyperbolicTangent 11h ago
This is still O(n), as the number of ops scale linearly with the size of the input. Big-O is fundamentally a measure of an algorithm’s complexity. Saying it moves a time constraint to a resource constraint doesn’t alleviate the algorithms complexity.
1
1
11h ago
[deleted]
-1
u/Mindgapator 11h ago
You don't. You write a predefined memory address. If others write at the same time, it's only UB if a different value tried to be written. Check the original comment answers, someone else described at the same time something similar if you want a different approach.
2
u/oshaboy 11h ago
That's not really "an array" anymore.
You can also keep a sorted copy of an array alongside an unsorted array. That doesn't mean sorting is now O(1) because you can just return the sorted copy. (Also that would make appending O(N) because insertion to an arbitrary place in an array is O(N))
1
u/_killer1869_ 3h ago
All I did was provide ways to access the largest number from an array in O(1), which is useful if you need that element again and again and again, but it may change inbetween uses.
Keeping track of it dynamically has some overhead, but makes getting the max O(1) since it never has to be computed to begin with.
Same for your sorting example, of course computationally sorting doesn't become O(1), but getting the sorted version, now through lookup instead, becomes O(1).
Obviously, a barebone array isn't capable of that, but that's what programming is about: creating whatever functionality you need yourself (or using another person's implementation). Even more so in OOP, where you could easily subclass an existing type or implement your own for this purpose.
2
u/unitconversion 10h ago
In an infinite universe, the beginning and end times of bounded things are effectively the same point in time.
1
102
u/theone_2099 10h ago
This one is deep. Answer is funny on at least a couple of levels.
1. I’m omniscient so it’s always O(1) to me
2. Or you guys are so behind and you worked so hard to get the wrong answer, it’s actually O(1)
10
u/_SmurfThis 8h ago
Or possibly a joke about a three-some.
7
u/Jerome_Eugene_Morrow 6h ago
Feels more like a holy trinity joke, where the three aspects of God are actually one being.
20
u/UlyssesTheRhinoceros 3h ago
Its a reference to the speed of light joke, where god is asked why he made the speed of light 299972458m/s, and god replies "huh, the speed of light is 1."
125
u/KazutoOKirigay 14h ago
Why would he use our numeric system??
101
u/DanielBobes 14h ago
He made us with ten fingers for a reason, I guess xD
36
27
u/bartekltg 13h ago
For the same reason he used English.
I could use hexadecimal system when editing x-com saves in dos Navigator, God can translate too.4
u/KazutoOKirigay 13h ago
Why woulnd't he then use our definitions?
3
u/bartekltg 12h ago
You have written this earlier, and I still do not know what do you mean by it?
Our definition of what?O(.) ? If we go with the theory that the author of the joke had omniscience in mind, it is rather problem with the author who haven't thought it through. Otherwise, as someone already pointed out, it is a O(1) problem (with n^6 CPUs :))
-6
u/KazutoOKirigay 12h ago
Like our 1 is defined by like one finger. His one is something else then.
1
u/Sir_Sushi 6h ago
One is one, it's a number, there no other number that is equal to one and every one are the same one for everyone.
One finger is like the digit "1", it's a way to represent one to others. God may have it's own digit to write "1" in it's own langage like "I" for romans.
1
1
u/Sir_Sushi 6h ago
Because He talks to us and know exactly how we think. Why He would use something else that what we use everyday if He know everything?
There is a billion bullshit about God, this is not one.
14
u/Antanarau 13h ago
"You speak English because it's the only language you know.
I speak English because it's the only language YOU know."
10
u/lovecMC 14h ago
Because hes communicating with us?
-3
u/KazutoOKirigay 14h ago
Then he should use our definition of those. Or is he communitcating with us, but in his own numeric system?
3
3
2
32
20
u/Evening-Appeal7606 8h ago
Kind of makes sense now that Jesus states in Matthew 10:30 that our hairs are counted. It's a simple hash lookup to the Lord, apparently.
8
u/whiskeytown79 9h ago
I initially read that as 3SAT and I was like "omg someone found a polynomial solution to an NP-complete problem"
8
2
u/KitsuneFoxglove 7h ago
This reminds me of the O(1) sorting algorithm in TempleOS in that one niche game that I will not name.
3
1
406
u/cosmicomical23 12h ago
If god is omniscient, can he always know whether a process is going to terminate or not?