Powering a number Problem: Compute an, where n E N. Naive algorithm: o(n Divide-and-conquer algorithm. C n2.n2 ifn is even n an-12. an-12. a if n is odd (n)=(n/2)+⊙(1)→7(m)=(gn) Day 4 Introduction to Algorithms L3.12Day 4 Introduction to Algorithms L3.12 Powering a number Problem: Compute a n, where n ∈ N. an = an/2 ⋅ an/2 if n is even; a(n–1)/2 ⋅ a(n–1)/2 ⋅ a if n is odd. Divide-and-conquer algorithm: T(n) = T(n/2) + Θ(1) ⇒ T(n) = Θ(lg n) . Naive algorithm: Θ(n)