There is an array related problem, the requirement is that time complexity is O(n) and space complexity is O(1).
If I use Arrays.sort(arr)
, and use a for
loop to one pass loop, for example:
public static int hello(int[]A){
Arrays.sort(A);
for(int i=0;i<A.length;i++){
....................
}
return ....;
}
So the loop will cost O(n) time. My question is: will Arrays.sort()
cost more time? If I use Arrays.sort()
, will this time complexity still be O(n)? And will Arrays.sort()
cost more space?
Arrays.sort()
to employ some magic, I think the question about what minimum time complexity it has is quite answerable, isn't it?Arrays.sort
, so whichever algorithm that uses. It's hard to tell what language this is (guessing Java), but standard library sorts are almost always comparison sorts.Arrays.sort
's time and space complexity?", which is really a question which shows no research effort, as this is fairly well-documented.