이진 트리에서 탐색할 때 평균 시간 복잡도는 O(log n)이 됩니다. 균형 이진 트리인 경우가 이에 속합니다.

그리고 최악의 경우에는 이진 트리가 사슬과 같이 연결된 형태로 이 경우에는 연결리스트와 같이 동작하기 때문에 시간 복잡도가 O(n)이 되게 됩니다.

​

평균 시간복잡도를 제대로 계산하기 위해서는 확률 분야에서 사용하는 테크닉을 이용해 계산을 해야 합니다.

​

아래는 영문으로 된 평균 시간 복잡도를 계산하는 방식입니다. 간략하게 설명하면 1번에 찾을 수 있는 확률, 2번 만에 찾을 수 있는 확률, ..., 이렇게 계산을 해서 기댓값을 구하는 방식으로 하시면 되겠습니다.

​

https://cs.stackexchange.com/questions/32090/proving-that-the-average-case-complexity-of-binary-search-is-olog-n

P.S. 위 답변에서 Big-O notation에 대해서 잘못된 내용을 알려주고 있어서 정정합니다.

​

Big O notation의 경우 해당 시간 복잡도를 n에 대한 식 f(n)으로 표기를 하였을 때 충분히 큰 n에 대해서 f(n) <= c*g(n) (c는 상수) 이 될 때 O(f(n)) = g(n) 으로 표기합니다.

즉 Big O notation은 최악의 경우를 기술하는데 사용하는 것이 아니라 해당 시간 복잡도가 Big O notation의 결과의 함수에서 계산한 시간 복잡도보다 더 적게 걸린다는 것을 의미합니다.

​

여기서 중요한 것은 "충분히 큰 n"이라는 부분인데, 그 이유는 n이 작은 경우에는 컴퓨터의 성능이 빠르기 때문에 계산 시간이 얼마 걸리지 않으므로 무시할 수 있고, n이 커지게 되면 그만큼 시간이 걸리기 때문에 n이 큰 경우에 시간이 대략 어느정도까지 걸릴 수 있다라는 것을 짐작하기 위한 지표로 사용합니다.