Give a tlg n algorithm that computes the remainder when x n

Question

Problem

1. Give a Θ(lg n) algorithm that computes the remainder when x n is divided by p. For simplicity, you may assume that n is a power of 2. That is, n = 2 k for some positive integer k.

2. Explain in English what functions are in the following sets.

a. n^O(1)
b. O(n^O(1))
c. O(O(n^O(1)))