What’s the order of growth of the running time of count function ? Provide an an
ID: 3871946 • Letter: W
Question
What’s the order of growth of the running time of count function ? Provide an annotated code snippet stating asymptotic runtime for various blocks (in Big-Oh notation).
// return number of distinct pairs (i, j) such that a[i] + a[j] = 0
public static int count(int[] a) {
int n = a.length;
Arrays.sort(a);
if (containsDuplicates(a)) throw new IllegalArgumentException("array contains duplicate integers");
int count = 0;
for (int i = 0; i < n; i++) {
int j = Arrays.binarySearch(a, -a[i]);
if (j > i) count++;
}
return count;
}
Explanation / Answer
/ return number of distinct pairs (i, j) such that a[i] + a[j] = 0
public static int count(int[] a) {
int n = a.length; =========> Runs only once
Arrays.sort(a);=========> Sorting takes O(n log n) at minimum for any comparision sort
if (containsDuplicates(a)) ======> I dont have code for this , as you did not attach lets assume best time it takes is O(n)
throw new IllegalArgumentException("array contains duplicate integers");
int count = 0;====> Runs only once
for (int i = 0; i < n; i++) {====> Runs n+1 time
int j = Arrays.binarySearch(a, -a[i]);===> As we know standard BS runs for O(log n) time
if (j > i) count++; ==> n time
}
return count;Runs only once
}
Total time complexity is
=> 1 + n + n log n (SORT) + (for loop)n*Logn (bsearch) + constant terms
=> n log n [The higher term]
=> O(n log n)
Thanks, let me know if its clear and understandable
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.