3
$\begingroup$

Searching for a number in an array is said to have a runtime of O(n) because there may be cases where the number doesn't exist in the array. In such cases, you'd have to have gone through the entire array, which is O(n).

But how about in the case where we know the number definately exists in the array? Does the runtime change then?

Also is there a way to find out the average number of searches it would have to do before a number is found in an array based on its size?

$\endgroup$
0
3
$\begingroup$

Regardless of whether the number is present in the array, all n elements will still be examined in the worse case. For example if searching for the number 5:

array1 = {6, 8, 3, 7, 8, 2}
array2 = {6, 8, 4, 9, 4, 5}

Searching array1 will require looping over all 6 elements (leading to 5 not being found). Searching array2 will also require examining all 6 elements, with the final element being 5 and the search returning true.

As for the average number of searches, I believe you are referring to the average number of elements examined? This is difficult. If you are wondering what the average case is for arrays of ints with length 6, you would need to generate all possible permutations of arrays of ints with length 6, then search them all for your desired number (say 5) and calculate the average. This will differ again if you only include permutations that have at least one element which is 5 (average will improve).

For a brute force search algorithm like this, all you can really be certain of is that the average case will be somewhere between the best best case O(1) (5 is first element of the array) and the worst O(n)

$\endgroup$
1
  • 2
    $\begingroup$ Good thing we have smarter ways for arguing about averages than brute force search. $\endgroup$
    – Raphael
    Jul 12 '13 at 14:51
2
$\begingroup$

The general idea for proving similar lower-bounds is what is called adversary arguments.

Let's assume we have an algorithm that check at most $n-2$ cells. We argue that the algorithm cannot be correct.

Consider an array $A$ which does not contain $x$. We will fix $A$ to have an $x$ later. We run the algorithm on $A$. When the algorithm finishes it has checked at most $n-2$ cells. Therefore there are two cell $a$ and $b$ which are not checked. The algorithm run on $A$ will return some answer. We now modify $A$ such that the algorithm will work as before and clearly returns an incorrect answer.

If the algorithm returns $a$ we put $x$ in $b$. If the algorithm does not return $a$ we put $x$ in $a$. In both cases the modified $A$ contains $x$. However, note that the algorithm never checks the value of $a$ or $b$, so this change in $A$ has no effect on algorithm's execution. Therefore, the algorithm run on modified $A$ will return the same answer that it was returning before the modification. But we modified $A$ such that the answer returned by the algorithm is incorrect. So the algorithm doesn't work correctly.

The only thing we assumed about the algorithm was that it accesses at most $n-2$ cells of the array. Therefore, no algorithm with this assumption can solve the problem correctly. In other words, any algorithm solving the problem correctly needs to check at lease $n-1$ cells.

This is called an adversary argument because we look at the execution of the algorithm on some input and adversely modify the input to make sure the algorithm fails.

This $n-1$ lower-bound is tight as there is an algorithm that checks the first $n-1$ cells and returns the correct answer (if we have seen $x$ in the these cell then we know the answer, if we haven't, then b assumption that $x$ is in $A$ we know that it must be in the last cell).


Average case:

The part above was for the worst-case analysis of deterministic algorithms. In principle one can use similar but more delicate adversary arguments to prove average-case lower bounds on deterministic algorithms (average case analysis of deterministic algorithms should not be confused with randomized algorithms). However, remember that we don't have the average case analysis. Average case analysis depends on the distribution of inputs that you assume. Below I will consider a two simple but usual distribution.

The general idea is to show that there are many inputs where the algorithm check too many cells.


I. The input is an array of size $n$ containing exactly one $0$ and $x=0$. All inputs are equally likely.

Note that the average number of cells checked by linear search is roughly $n/2$. We show that this is tight up to a constant factor and no algorithm can have a better average case. Note that there are $n$ possible inputs each with probability $1/n$.

Assume that there is an algorithm that solves the problem. Consider the execution of the algorithm on all $0$ array. (This is not a possible input that we are interested in, however we can run the algorithm on whatever we like). The algorithm will check some number of cells. We consider the first $n/2$ cells that it checks (they don't need to be the first cells of the array). Let me call these cells $S$. Now consider all possible inputs that have zeros in these cells. There are roughly $n/2$ possible inputs of this form. We argue that for $n/2-1$ of these the algorithm needs to check at least $n/2$ cells. If stops before checking $n/2$ cells, and returns some answer, that answer should work for all of these inputs. However, the answer cannot be correct for more than one of them. These $n/2-1$ inputs contribute $1/n * n/2 * (n/2-1)$ to the total average number of cells that algorithm checks. So independent of how the algorithm runs on other possible inputs, the average will be at least $n/4-1$.


II. Now assume that we have arrays filled with $0$ and $1$ and there can be any number of them, and all are equally likely. W.l.o.g. let's assume $x=0$. Note that there are $2^n-1$ inputs.

The linear search algorithm checks on average $$\sum_{k=1}^{n-1} k2^{n-k}2^{-n} = O(1)$$ cells. So in this case we cannot prove any non-trivial lower bound.

$\endgroup$
6
  • $\begingroup$ I did not satisfied with your argument, may be there is a randomized algorithm, such that b and a are in different places in different execution. $\endgroup$
    – user742
    Jul 17 '13 at 15:31
  • $\begingroup$ @Saeed, we are talking about deterministic algorithms, that is why the execution is going to be the same. If you have other models then this argument does not apply in this form. For example, it is easy to see that a nondeterministic algorithm can find the answer in $O(1)$. $\endgroup$
    – Kaveh
    Jul 18 '13 at 5:59
  • 1
    $\begingroup$ I said randomize not nondeterministic $\endgroup$
    – user742
    Jul 18 '13 at 9:39
  • $\begingroup$ @Saeed, and I replied that I am only talking about the deterministic model, not other models. Randomized algorithms are not mentioned in this question. If you have a question about randomized algorithms you should ask a new question. $\endgroup$
    – Kaveh
    Jul 18 '13 at 10:11
  • $\begingroup$ If you don't know that randomized algorithm can be deterministic or non deterministic (like normal algorithm) then you can ask it in new question. But to modify your current algorithm, if you put a,b as output of the second algorithm then you can say if a and b are different then is non deterministic, but while you did not mentioned this, and output of the algorithm is just position of element (or yes/no),you can not argue on this even on deterministic algorithms. $\endgroup$
    – user742
    Jul 18 '13 at 11:44
1
$\begingroup$

Searching time in array might be faster the $\mathcal O(n)$ but such searches uses some knowledge about that array.

For instance there is something like Binary search algorithm which have much better complexity of searching for element. However this search method assumes that array is sorted in ascending order. Thanks to this assumption binary search works in $\mathcal O(\log n)$ but you need to take some extra effort to store this array sorted at all time.

However if array is arbitrary then it's a bit more complicated.

Let's start with something called Online algorithm. More precisely let's take a look on list update problem. In this problem you assume that some search queries might occur more often then other so it would be more efficient to update list/array when search is made. This will let you to reduce search time if some elements are searched much more ofthen then other.

Now let's look back at the original problem, searching arbitrary array, having no knowledge about it structure. It should be obvious that searching element in array has time complexity $\mathcal O(n)$, but can we be more precise on this? In fact we can, it involves some probability theory and basic calculus. It's quiet fun to do this by yourself so I'll just point out steps which you need to take in order to calculate avarage number of elements examined.

  1. Assume that array contains unique elements from 1 to $n$.
  2. Assume that all permutations of elements are equally probable, so each permutation has probability $\frac{1}{n!}$.
  3. Write down search procedure and determine how many times each step will be executed.
  4. Find general formula for any length of array.

You can also computer someting called Probability-generating function which is usefull for analysis of algorithms.

As for book reference on that topic I can recommend The Art of Computer Programming by Donald Knuth.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.