[CODE]
(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m)
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))
[/CODE]

T(n) = T(n/2) + c 꼴이고 Master theorem 을 적용해보자.

나오므로 수행시간은

[CODE]
(define (expmod-louise base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (* (expmod-louise base (/ exp 2) m)
                       (expmod-louise base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod-louise base (- exp 1) m))
                    m))))
[/CODE]

Louis 가 만든 코드의 프로시져 수행시간을 보자.

T(n) = T(n/2) + T(n/2) + c = 2T(n/2) + c

역시 master theorem 을 적용해보면,

이므로 이 된다.

수행시간 증명이 잘 생각나지 않아 오랜만에 책을 뒤적여 Master theorem 을 봤습니다.