0
$\begingroup$

I have an integer array and some x integer number. I'm looping through this array and compare each element with x, if there exists the exact element, the algorithm ends.

The best case is B(n) = 1, the worst is W(n) = n.

How should I count the average-case time complexity though? Maybe I'll try to precise my question a bit:

  1. I have two cases here: searched element is in the array, and searched element is NOT in the array. Is this enough to just count the time complexity for some probability that the element can be found in the array?

  2. If the element is in the array the time complexity is $n/2$, if it's not then it's simply $n$. But how can I count this using the probability?

$\endgroup$
  • $\begingroup$ Can your array have duplicate elements? That will complicate matters. $\endgroup$ – Rick Decker Jun 7 '13 at 13:33
1
$\begingroup$

If the probability the element is in the array is $p$, the average run time is $p\cdot \frac n2+(1-p)n=n(1-\frac p2)$

$\endgroup$
  • $\begingroup$ It may not be true if the element is always at the same place no? you are assuming that the element can be only once in the table and that is place has a uniform probability. But I'm not sure those assumptions are contain in the question. $\endgroup$ – wece Jun 7 '13 at 13:33
  • $\begingroup$ @wece: OP stated that the complexity if present was $\frac n2$, which assumes it is there once in a random location. I made use of that. You are correct that if it is present multiple times, the time to find the first will be reduced. $\endgroup$ – Ross Millikan Jun 7 '13 at 13:46
  • $\begingroup$ Yep i saw the $n/2$ but I wasn't sure if it was a wild guess or a real hypothesis. $\endgroup$ – wece Jun 7 '13 at 13:49

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.