원서 보고 공부 중인데 거기서 나온 문제입니다.

시간 복잡도 계산이 헷갈려서 질문 드립니다.

아래에 있는 것이 문제이고, 수도코드입니다.

//울타리의 판자를 모두 색칠하기

Algorithm2 (int first_board, int last_ board)

if ( first_board == last_board)

// 보드가 하나 밖에 없으므로 색칠함

paint();

else

          // 보드들을 반으로 나누기

int middle_board = ( first_board + last_board ) / 2

Algorithm2 (first_board, middle_board)

Algorithm2 (middle_board, last_board)

End Algorithms2

해설의 정답은 O(logN + N) = O(N) 입니다.

둘로 나누는 횟수 logN + paint 횟수 N 를 더해 O(logN + N) 이 나왔고 그건 O(N)이 됩니다.

궁금한것은 처음이 왜 O( logN+N)이냐는 것입니다. 특히 logN이요.

재귀함수의 호출 횟수는  logN번이 아니라 더 많이 수행하지 않나요?

ex) N=8이면

8 - 4 - 2 - 1

      - 1

        - 2  - 1

               -1

   - 4 - 2 - 1

      - 1

        - 2  - 1

               -1 

이렇게 나누어 질텐데요. 8에서 1로 나눠지기까지 step의 수가 log8 = 3인건 알겠습니다.

근데 재귀 함수가 호출된 횟수는 2*2*2 = 8 이니까요. 왜 재귀함수의 호출 수가 아닌 step의 수인 logN을 시간복잡도로 쓸까요?

궁금합니다.