# Asymptotic Analysis and Fibonacci Number

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?

Â© BrainMass Inc. brainmass.com March 4, 2021, 6:26 pm ad1c9bdddfhttps://brainmass.com/math/number-theory/asymptotic-analysis-fibonacci-number-45149

#### Solution Preview

Please see the attached file for the complete solution.

Thanks for using BrainMass.

Q.1

For a number x, with 1 x p, the number can be computed with at most

modulo p multiplications.

It is true. By Modular Arithmetic, we know that

mod p) (b mod p)] mod p

mod ] mod p

So, when we compute , it suffices to write n in the form of

Since any positive integer can have a binary code ...

#### Solution Summary

Asymptotic Analysis and Fibonacci Number are investigated.