Duplicate Numbers
The following program can find out if an integer array contains duplicate numbers.
Give the best-case and worst-case runtime complexity using Big-O notation.
public static boolean containsDuplicates (int[] array, int number) {
int n = array.length;
for (int i = 0; i

Question

Duplicate Numbers
The following program can find out if an integer array contains duplicate numbers.
Give the best-case and worst-case runtime complexity using Big-O notation. 
public static boolean containsDuplicates (int[] array, int number) {
  int n = array.length;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i !== j && array[i] === array[j]) {
        return true;
      }
    }
  }
  return false;
}

public static void main ( String[] args ) {
  int[] randomNumbers = { 10, 2, 9, 15, 22 };
   containsDuplicates(randomNumbers, 27);
}

1: Best Case
2: Worst Case

BlackTom AI · Accepted Answer

Nested loops produce quadratic time behavior, so the worst case grows on the order of n^2, while an early return can make the best case constant.

1) Relevant knowledge points and concepts
- Big-O measures asymptotic upper bounds as n (array length) grows.
- Best-case runtime: smallest number of steps possible for some input of size n.
- Worst-case runtime: largest number of steps for any input of size n.
- Nested loops that examine all pairs (i, j) typically produce O(n^2) work; an early return can make the best case much smaller.

2) Step-by-step reasoning
- Outer loop: for i = 0 to n-1 (n iterations).
- Inner loop: for j = 0 to n-1 (n iterations each time).
- Condition checked: if (i != j && array[i] == array[j]) return true.
- The inner condition uses short-circuit: when j == i the equality test is skipped, but the loop iteration still occurs.

3) Calculations and intermediate steps
- Best case: A duplicate is found immediately on the first useful comparison (for example i=0, j=1 and array[0] == array[1]). The code will do a fixed small number of operations (checking i!=j for j=0, then checking j=1 and comparing the two elements) and return. This number of steps does not grow with n, so best-case complexity = O(1).
- Worst case: No duplicates exist (or the only duplicates are discovered after examining all pairs). The loops will iterate roughly n times for i and n times for j, performing about n*(n-1) element comparisons (since comparisons skip when i==j), which is n^2 - n. Asymptotically this is O(n^2).

4) Why the correct answer is correct
- O(1) (best case) is correct because an immediate duplicate causes an immediate return after a constant number of checks independent of n.
- O(n^2) (worst case) is correct because the nested loops force checking on the order of n^2 pairs when no early return occurs, dominating lower-order terms.

5) Why other options are incorrect
- O(n) would imply a single linear pass can decide duplicates here, but the given code compares pairs in nested loops, so it can do much more work than linear.
- O(n log n) is typical for efficient sorting-based algorithms, but this code does not sort or use divide-and-conquer and therefore is not n log n.

6) Conclusion
Best-case runtime: O(1). Worst-case runtime: O(n^2). This matches the provided answers.

类似问题

What is the big-O of the worst-case time cost of inserting an element somewhere into an array of size n? Select the tightest bound that holds.

Which of the following is a big-O description that applies to the function g(n) = 18log n + 2n + 3n log n? Select the tightest bound that holds.

What is the time complexity of the following Python code? A = np.zeros(5) n = np.size(A) for i in range(n): A[i] = A[i]2 print(A) for j in range(i,n): for k in range(i,j): A[j] = A[i]/5 for i in range(n): print(A) A[i] = A[i]2 for j in range(i, n): A[j] = A[i]/5

What is the time complexity of the following Python code? A = np.zeros(5) n = np.size(A) for i in range(n): A[i] = A[i]**2 for j in range(i, n): A[j] = A[i]/5 print(A)

What is the time complexity of the following Python code? A = np.zeros(5) n = np.size(A) for i in range(n): A[i] = A[i]**2 for j in range(n): A[j] = A[i]/5

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单