A \"magic square is an N by N matrix of numbers in which each of the numbers fro

Question

A "magic square is an N by N matrix of numbers in which each of the numbers from 1.N2 occurs exactly once, and each of the rows and columns and the two main diagonals adds up to the same value. For example, here is a 3 by 3 magic square 294 753 618 Assume that we have been provided with a function bool isMagic (Int sq, int N) that tests an N by N square sq to see if it is magic. Assume that isMagic has O(N2) worst-case complexity and O(N) average-case complexity The following code attempts to find a magic square of a specified size 001 void generateMaicSquare(int s, int N) 002 003 bool more=true 004 vectorcint> numbers 005 for (int i = 1: i

Explanation / Answer

lines 3 to 4: O(1)
There are exactly 2 statements. And each of these takes a constant time.
Answer: A

-----

line 6: O(1)
This is just 1 operation which takes constant time.
Answer: A

-----

lines 5 to 6: O(N^2)
Reason: Line 6 is executed N^2 times.
Answer: H

-----

lines 13 to 14: O(1)
There are two lines each one takes constant time - one assignment and one increment operation.
Answer: A

-----

lines 11 to 15: O(N)
Reason: The statements inside lines 12 to 15 are executed N times.
Answer: E

-----

lines 10 to 16: O(N^2)
Reason: The block from 11 to 15 is executed N times.
And we already calculated above that lines 11 to 15 have complexity O(N)
So, total complexity is O(N^2)
Answer: H

-----

lines 8 to 9: O(N^2)
Reason: std::next_permutation takes linear time complexity.
Here we have N^2 elements. So, it takes O(N^2) time complexity.
Answer: H

-----

lines 7 to 16: O((N^2)!)
Line 8 to 15 takes O(N^2) + O(N^2) = O(N^2)
The while condition has two parts
* more: This gives true as long as new permutation can be found for N^2 numbers. So, it gives true (N^2)! times.
* isMagic: At worst none of it magic square. Total number of permuations = (N^2)!
So, we may run this condition (N^2)! times and each of these times, the inner statements will run O(N^2) times.
So, total is (N^2)! * (N^2) = ((N^2)+1)! = (N^2)!
Answer: N

-----

lines 3 to 16: O((N^2)!)
Same as from 7 to 16 because other statements only cause O(N^2).
Therefore, N^2 + (N^2)! = O((N^2)!)
Answer: N

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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