What is the time complexity of the following code?
#include <bits/stdc++.h>
using namespace std;
void convert(int arr[], int n)
{
int temp[n];
memcpy(temp, arr, n*sizeof(int));
sort(temp, temp + n);
unordered_map<int, int> map;
int sort_index = 0;
for (int i = 0; i < n; i++)
map[temp[i]] = sort_index++;
for (int i = 0; i < n; i++)
arr[i] = map[arr[i]];
}
void printArr(int arr[], int n)
{
for (int i=0; i<n; i++)
cout << arr[i] << " ";
}
int main()
{
int arr[] = {10, 20, 15, 12, 11, 50};
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 arr[], int n)
{
int temp[n];
memcpy(temp, arr, n*sizeof(int));
sort(temp, temp + n);
unordered_map<int, int> map;
int sort_index = 0;
for (int i = 0; i < n; i++)
map[temp[i]] = sort_index++;
for (int i = 0; i < n; i++)
arr[i] = map[arr[i]];
}
void printArr(int arr[], int n)
{
for (int i=0; i<n; i++)
cout << arr[i] << " ";
}
int main()
{
int arr[] = {10, 20, 15, 12, 11, 50};
int n = sizeof(arr)/sizeof(arr[0]);
convert(arr , n);
printArr(arr, n);
return 0;
}
A. O(n)
B. O(1)
C. O(n log n)
D. O(n2)
Answer: Option C
Join The Discussion