For ANY distribution.
Best case: n = "a*".
This will take len(n)/2
steps, so the best case is: O(len(n))
Worst case: n = "b*".
This will take len(n)
steps, because you have to go through the entire array. So worst case is O(len(n))
Average case is bounded by best case and worst case. That is, O(len(n)) <= average case <= O(len(n))
. It follows that the average case complexity is O(len(n))