0

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?

khernik
  • 1,369

1 Answers1

2

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)$

Ross Millikan
  • 374,822
  • 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. – wece Jun 07 '13 at 13:33
  • @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. – Ross Millikan Jun 07 '13 at 13:46
  • Yep i saw the $n/2$ but I wasn't sure if it was a wild guess or a real hypothesis. – wece Jun 07 '13 at 13:49