Q.1 For a number x, with 1< x < p, the number x^n mod p can be computed with at most 2log2 n modulo p multiplications.
Asymptotic notation questions
Q.2 2^(2n) = O(2^n)
Q.3 log*n = O(log*(log n))
Q.4 The sqrt n th Fibonacci number can be computed and written in O(log n) time
Please see the attached file for the fully formatted problems.
The answer should include TRUE or FALSE and an explanation?
Asymptotic Analysis and Fibonacci Number are investigated.