Explore BrainMass

Explore BrainMass

    Asymptotic Analysis and Fibonacci Number

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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 ad1c9bdddf
    https://brainmass.com/math/number-theory/asymptotic-analysis-fibonacci-number-45149

    Attachments

    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.

    $2.49

    ADVERTISEMENT