I’m doing a comparison between brute force search and my custom search approach.

A problem arose in estimating the complexity of a brute-force search. As part of the search, I need to check whether the specified elements are in an unsorted list of elements.

I will give a simplified example for a list of integers. I have an integer list with elements [1..100_000]. I go through all the elements linearly and calculate how many comparisons I need to do to find all the searched elements.

My results are next:

1. For 1 searched element: near 50_000 comparisons, equals to O(N/2). It is clear for me. The best case is 1 the worst is 100_000, and the everage is 50_000.
2. For 2 searched elements: near 65_000 comparisons. But why? What is mathematical or Computational complexity?
3. For 3 searched elements: near 75_000 comparisons. But why? What is mathematical or Computational complexity?

Screenshot of the my benchmark with 1_000 runs:

My code is next in Java.
I check the same elements, but the copy of the list is shuffled before each search.

public static void main(String[] args) {
        List<Integer> values = IntStream.range(1, 100_000).boxed().toList();

        List<Integer> results1 = new ArrayList<>();
        List<Integer> results2 = new ArrayList<>();
        List<Integer> results3 = new ArrayList<>();

        List<Integer> list1 = List.of(1);
        List<Integer> list2 = List.of(1, 2);
        List<Integer> list3 = List.of(1, 2, 3);

        for (int i = 0; i < 1000; i++) {
            results1.add(search(values, list1));
            results2.add(search(values, list2));
            results3.add(search(values, list3));
        }
        System.out.println("Search 1: " + results1.stream().mapToInt(i->i).average().getAsDouble());
        System.out.println("Search 2: " + results2.stream().mapToInt(i->i).average().getAsDouble());
        System.out.println("Search 3: " + results3.stream().mapToInt(i->i).average().getAsDouble());
    }


    private static int search(List<Integer> list, List<Integer> search) {
        List<Integer> values = new ArrayList<>(list);
        Collections.shuffle(values);

        int i = 0;
        int found = 0;
        for (; i < values.size(); i++) {
            if (search.contains(values.get(i))) {
                ++found;
            }
            if (found == search.size()) {
                break;
            }
        }
        return i+1;
    }