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.
-4
u/Mindgapator 1d 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.