Fermat\'s Last Theorem states that no three positive integers a, b, and c can sa

Question

Fermat's Last Theorem states that no three positive integers a, b, and c can satisfy the equation an + b n = cn for any integer value of n greater than two. a. Write a psuedocode algorithm to empirically prove this theorem by exhaustively checking for all combinations of integers less than or equal to n. Hint: One way to do this is to generate all permutations of 4 variables, n, a, b, c, (skipping n = 1 or 2) then evaluate the expression for each permutation. Let n go from 3 to some large value N. b. What is the TIME COMPLEXITY of your algorithm in BigO notation?

Explanation / Answer

Assuming n is ranging from 3....N.
so we can have n,a,b,c (number of arrangments consisting of four entries out of N enteries) = N! /(N-4)!.Checking every arrangement is of O(1). The number of arrangements are in the order of O(N^2). Hence the time complexity is of O(N^2)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.