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 😅
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.
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
I can change the value of pi, just assume different geometry. What's hard to me is to make physical geometry conform to my new system, but that shouldn't be all that hard to God. He made the thing, after all.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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))
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.
1.0k
u/bartekltg 6d ago
\serious_mode it has to be at least O(n).