Worst case:   no k or find k in a[N-1]   (N)

Average case:   find k "in the middle" of a   (N/2)

Could devise "overall average" if we know likelihood of each case.

If not, take pessimistic view ... worst case.

In fact, both worst and average cases grow linearly.