recategorized by
554 views
0 votes
0 votes
What is the average case time complexity of the best sorting algorithm for an array having 2^n^2 elements .

I know that the best sorting algorithm is no better than O(n log n).Please answer in terms of the asymptotic notation.
recategorized by

2 Answers

0 votes
0 votes
I think:

For comparison based algorithms: O($n^{2}2^{n^{2}}$)

And for non-comparison based algorithm, if the numbers are in fixed range or the largest number is not a big number such that the number of digits doesn't depend on n: O($2^{n^{2}}$)
0 votes
0 votes
I we use merge sort as the algorithm(which is best for worst case) then,

The time complexity T(n) = n^2* 2^n^2

Related questions

0 votes
0 votes
1 answer
1
1 votes
1 votes
1 answer
4
iarnav asked May 4, 2019
834 views
I’ve seen this wikipedia article – https://en.wikipedia.org/wiki/Comparison_sortAlso see this link – https://gateoverflow.in/32948/minimum-number-of-comparisonshttp...