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