# Tag Info

## Hot answers tagged average-case

Accepted

### Proving that the average case complexity of binary search is O(log n)

I think most text book will provide you a good proof. For me, I can show the average case complexity as follows. Assuming a uniform distribution of the position of the value that one wants to find ...
• 839
Accepted

### What is the time complexity of this atrocious algorithm?

We can write a recurrence relation for this procedure as follows. Let $T(n)$ be the worst-case time for running sort on a list of length $n$. When calling ...
• 270k