What is the time complexity of the following code that determines the number of inversions in an array?
Posted: Wed Jul 13, 2022 7:42 pm
int InvCount(int arr[], int n)
{
int count = 0;
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (arr > arr[j])
count++;
return count;
}
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
{
int count = 0;
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (arr > arr[j])
count++;
return count;
}
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)