What is the time complexity of the following Python code snippet? Python def…
2024
What is the time complexity of the following Python code snippet?
Python
def find_duplicates(arr):
duplicates = []
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[i] == arr[j]:
duplicates.append(arr[i])
return duplicates
- A.
O(n)
- B.
O(log n)
- C.
O(n^2)
- D.
O(1)
Attempted by 87 students.
Show answer & explanation
Correct answer: C
Answer: O(n^2)
Explanation:
The outer loop iterates over each element (approximately n iterations).
For each iteration of the outer loop, the inner loop compares the current element with the remaining elements. On average the inner loop runs on the order of n iterations across all outer iterations, giving about n*(n-1)/2 total comparisons.
Each comparison and each list append performs constant work (append is amortized O(1)), so the total work is proportional to the number of comparisons, which is O(n^2).
Therefore the overall time complexity of the function is O(n^2).
Note: The extra space used for the duplicates list can be O(n) in the worst case, but the question asks for time complexity.