Purpose: To practice analyzing algorithms to assess their run time complexity. D

Question

Purpose: To practice analyzing algorithms to assess their run time complexity. Degree of Difficulty: Easy Analyze the following Python code, and determine the worst-case time complexity. Justify your work with a brief explanation. 1def check_range (square): 3Purpose: 4 6 Pre: 8 Check that the square contains only the numbers 1 .. . n, where n is the size of the of one side of the square square a 2D list of integers, n lists of n integers Post: nothing 9 Return True if 10 the square contains only integers 1 n False otherwise 12 | n = len(square) 13 for i in range (n): 14 15 16 17 18 return True for j in range (n) val = square [1] [j] if val not in range (1, n+1): return False What to hand in Include your answer in the a7.txt document Clearly identify your work using the question number Evaluation . 2 marks: Your result was correct and used big-O notation. 1 mark: You identified a size parameter 3 marks: You correctly analyzed the loop. Lines 13-17.

Explanation / Answer

Here we have two Nested FOR loops:

Outer FOR loop runs for i = 0 to i=n-1 : n times

Inner FOR loop runs for j = 0 to j=n-1 : n times

Hence Time Complexity: n x n = O(n^2)

Size parameter: n

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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