which one will be faster?

let's say i have an array, size 40. and the element im looking for is in position 38. having a simple loop, it will 开发者_如何学JAVAtake 38 steps right? but, having, 2 loops, running in parallel, and a variable, "found" set to false, and changes to true when the element is found.

the first loop, will start from index 0 the second loop, will start from index 40.

so basically, it will take only, 4 steps right? to find the element. the worst case will be if the element is in the middle of the array. right?

---

It depends how much work it takes to synchronize the state between the two threads.

If it takes 0 work, then this will be, on average, 50% faster than a straight through algorithm.

On the other hand, if it takes more work than X, it will start to get slower (which is very likely the case).

From an algorithm standpoint, I don't think this is how you want to go. Even 2 threads is still going to be O(n) runtime. You would want to sort the data (n log n ), and then do a binary search to get the data. Especially you can sort it 1 time and use it for many searches...

---

If you're talking about algorithmic complexity, this is still a linear search. Just because you're searching two elements per iteration doesn't change the fact that the algorithm is O(n).

In terms of actual performance you would see, this algorithm is likely to be slower than a linear search with a single processor. Since very little work is done per-element in a search, the algorithm would be memory bound, so there would be no benefit to using multiple processors. Also, since you're searching in two locations, this algorithm would not be as cache efficient. And then, as bwawok points out, there would be a lot of time lost in synchronization.

---

When you are running in parallel you are dividing your CPU power into two + creating some overhead. If you mean you are running the search on a say, a multicore machine, with your proposed algorithm then the worse case is 20 steps. You are not making any change in the complexity class. So where those 4 steps, that you mentioned, are coming from?

---

On average there is no different in runtime.

Take for example if you are searching for an item out of 10.
The original algorithm will process in the following search order:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

The worse case is the last item (taking 10 steps).

While the second algorithm will process in the following search order:

 1, 3, 5, 7, 9, 10, 8, 6, 4, 2

The worse case in this scenario is item 6 (taking 10 steps).

There are some cases where algorithm 1 is faster.
There are some cases where algorithm 2 is faster.

Both take the same time on average - O(n).

---

On a side note, it is interesting to compare this to a binary search order (on a sorted array).

4, 3, 2, 3, 1, 4, 3, 2, 4, 3

Taking at most 4 steps to complete.