What’s the order of growth of the running time of count function ? Provide an an
ID: 3871950 • 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).
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++) {
for (int j = i+1; j < n; j++) {
int k = Arrays.binarySearch(a, -(a[i] + a[j]));
if (k > j) count++;
}
}
return count;
}
Explanation / Answer
Answer:
The order of growth of the running time of this code will be O(n^2)
Explaination:
In this piece of code , there are two for loops.
One loop runs from 0 till n , so its total time will be O(n)
Second loop runs from 1 to n , its order will be O(n)
So total tunning time of the code will be O(n) * O(n) = O(n^2)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.