추가 질문이 있어서 댓글 남깁니다. 답변해주신 것처럼 가장 하위단계에서부터 올라갈때는 O(n)이 맞는데 하위 단계로 가기 위해서 주어진 n을 n, n/2, n/4, ... , 1이 될때까지 분할하는 과정이 필요한데 이 과정에 필요한 시간이 O(log N) 이므로 총 시간복잡도는 O(N logN)이 되어야 하는게 아닌가요?

O(nlogn)은 O(logn) 코드가 n번 반복되어야 하는데 이 경우는 그렇지 않은 것 같습니다 (분할하는 과정이 n번 반복되지 않기 때문입니다). 제가 생각하기에 시간 복잡도를 구하는 가장 간단한 방법은 `consecutive_sum`이 몇번 호출되는지 계산하는 것 입니다 (1 + 2 +4 + .. + n = 2n번 호출됩니다). `consecutive_sum`함수 안에 나머지 연산은 모두 O(1)이기 때문입니다.

다른 알고리즘의 분석과 조금 혼동해서 생각했던것 같습니다. 답변 감사드립니다!

넵! 재귀함수의 시간복잡도를 분석할때는 재귀 방정식을 사용할 수 있습니다 - [링크](https://jhnah917.tistory.com/41) 참고하세요!