How to find the average runtime of this program def search(lst, x):
for item in lst:
$\space \space\space\space $   if item == x:
$\space \space\space\space $$\space \space\space\space $return True
$\space \space\space$ return False
if the allowed input is a random list of length n made up of random elements from {1,2....10} which can be repeated
How do I prove that the average runtime is $\theta$(1)
I've tried so many ways but i keep on getting $\theta$(n)
 A: I would assume your list is not sorted, but each element is a random selection from $1$ to $10$.  The problem does not say that, but it seems the appropriate assumption.  Punch the problem setter in the nose for me.  You are looking for whether there is at least one $x$ in the list.  For large $n$ you find one with probability approaching $1$.  The chance of stopping at $i$ loops is $\frac {9^{i-1}}{10^i}$ because you need $i-1$ values that are not $x$ followed by $x$.  The expected run time is $\sum_{i=1}^n\frac {i9^{i-1}}{10^i}+\frac {9^n}{10^n}$.  The first term converges to a constant, so is $O(1)$.  The second term goes to zero, so the sum is $O(1)$
A: If the list is literally $\{1,2,3,4,5,6,7,8,9,10\}$, then the algorithm is guaranteed to finish in $10$ steps. That's constant time.
If the list is of variable length $n$, but the list is sorted in ascending order starting from $1$, then you know that the algorithm will return True if $x\leq n$, and False otherwise. That's one comparison, and so it's constant time.
If the list is of variable length $n$, but the list is sorted in ascending order starting from $a$, then you know that the algorithm will return True if $a \leq x\leq n$, and False otherwise. That's two comparisons, and so it's constant time.
But if the list is of variable length $n$ and sorting is not guaranteed, then you must check every item to know for sure whether $x$ is in the list. That requires checking $n$ elements and so it's linear time.
