What is the auxiliary space complexity of the given code?
#include <bits/stdc++.h>
using namespace std;
void convert(int a[], int n)
{
vector <pair<int, int> > vec;
for (int i = 0; i < n; i++)
vec.push_back(make_pair(a[i], i));
sort(vec.begin(), vec.end());
for (int i=0; i<n; i++)
a[vec[i].second] = i;
}
void printArr(int a[], int n)
{
for (int i=0; i<n; i++)
cout << a[i] << " ";
}
int main()
{
int arr[] = {10,8,2,5,7};
int n = sizeof(arr)/sizeof(arr[0]);
convert(arr , n);
printArr(arr, n);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
void convert(int a[], int n)
{
vector <pair<int, int> > vec;
for (int i = 0; i < n; i++)
vec.push_back(make_pair(a[i], i));
sort(vec.begin(), vec.end());
for (int i=0; i<n; i++)
a[vec[i].second] = i;
}
void printArr(int a[], int n)
{
for (int i=0; i<n; i++)
cout << a[i] << " ";
}
int main()
{
int arr[] = {10,8,2,5,7};
int n = sizeof(arr)/sizeof(arr[0]);
convert(arr , n);
printArr(arr, n);
return 0;
}
A. O(1)
B. O(n)
C. O(log n)
D. O(n log n)
Answer: Option B
Join The Discussion