이진 탐색 알고리즘의 시간복잡도가 lgn인 이유가 탐색하는 범위가 절반씩 줄어들어서란건 이해했습니다. 그런데 j가 2m씩 커지는 건 탐색 범위가 줄어드는게 아닌데 왜 lgn씩 반복되는건지 잘 이해가 되지 않아 댓글 남깁니다. 저는 단순히 반복문이 2개가 반복되어 n^2이라 생각했습니다.

반복문이 2개고 i가 2배씩이 아니라 +1만큼 커진다면 말씀하신대로 n^2가 맞습니다. 그런데 반복문이더라도 몇 번 반복하게 되는지 확인해야 합니다. while문에서 반복하는 횟수는 n번이 아니기 때문에 다르게 계산됩니다.