Recursive squaring Theorem:n Algorithm: Recursive squaring Time=o(g n Proof of theorem. (Induction on n) Base(n=1) F2F「1 F1F0」[10 Day 4 Introduction to Algorithms L3.15Day 4 Introduction to Algorithms L3.15 Recursive squaring n F F F F n n n n   =  − + 1 0 1 1 1 1 Theorem: . Proof of theorem. (Induction on n.) Base (n = 1): . 1 1 0 1 1 1 0 2 1   = F F F F Algorithm: Recursive squaring. Time = Θ(lg n)