# Finding average-case time complexity

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?

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

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)$
• @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 7 '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 7 '13 at 13:49