Finding average case complexity with probability

Question

Lets say we have a string n, which can either be populated with "a"s or "b"s ex: n = "aaabbbab", "ababababab" and so on. and we define a function called

HalfA(n):
  count a = 0;
  for each i in n:
    if n == 'a'
        i++;
     if i >= n.length/2
       return true 
  return false     

and if n has a uniform distribution, what is the average case complexity of halfA. Intuitively, I believe it to be len(n) but I'm not sure how to show this. And suppose a is more probable than b, and its not a uniform distribution, how do I calculate the average case then?

Answer 1

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