Let's imagine we want to search for an element in an array of n elements and we can create as many threads as we want. Let's assign a separate thread for each element of the array and consider that the comparison operation is a lot more expensive than creating threads. Is it valid to say that such searching algorithm is O(1)?

Code:

```
import java.util.concurrent.atomic.AtomicBoolean;

public class scratch {
    static int[] a = new int[100];
    static final int n = 3;
    static boolean expensiveCompare(int pos) {
        try {
            Thread.sleep(1000);
        } catch (InterruptedException e){}
        return a[pos] == n;
    }

    static AtomicBoolean answer = new AtomicBoolean(false);

    public static void main(String... args) {
        long start = System.currentTimeMillis();
        a[2] = 3;
        Thread[] threads = new Thread[100];
        for(int i=0; i < 100; ++i) {
            final int k = i;
            threads[i] = new Thread(new Runnable() {
                @Override
                public void run() {
                    if(expensiveCompare(k)) {
                        answer.compareAndExchange(false, true);
                    }
                }
            });
            threads[i].start();
        }

        for(int i = 0; i < 100; ++i) {
            try {
                threads[i].join();
            }catch (InterruptedException e) {}
        }

        System.out.println("Elapsed: " + (System.currentTimeMillis() - start));
        System.out.println("Answer:" + answer);
    }
}

```

Prints: "Elapsed: 1000"

```
public class scratch {
    static final int n = 3;
    static int[] a = new int[100];
    static boolean answer = false;

    static boolean expensiveCompare(int pos) {
        try {
            Thread.sleep(1000);
        } catch (InterruptedException e) {
        }
        return a[pos] == n;
    }

    public static void main(String... args) {
        long start = System.currentTimeMillis();
        a[2] = 3;
        for (int i = 0; i < 100; ++i) {
            answer |= expensiveCompare(i);
        }
        System.out.println("Elapsed: " + (System.currentTimeMillis() - start));
        System.out.println("Answer:" + answer);
    }
}

```

Prints: "Elapsed 100000".