this whole time we will think of n as 2 i mean int n =2; took a array of 2 elements let's suppose [3,1]
now you have to sort it in ascending order
import random
arr = [2, 3] if random.randint(0, 1) == 1: # 50% chance to swap (1 out of 0 or 1) arr[0], arr[1] = arr[1], arr[0] print(arr) it will swap elements in O(1)
and it's sorting so, it's best case is O(1) so, worst case is O(n!)
so actually their is a chance that in first iteration
we will get sorted array
but chances and probablity are 50%
so can we say that O(1) sorting algorithm exist
(before downvoting tell me what's wrong with my question and what should i do now)
Conclusion: after reading all your comments i have realised that we cant say a sorting algorithm is actually a sorting algorithm if it cant sort up to a fixed length
NO SORTING TAKES O(NLOGN) TIME
but i think in len(array) = 2 it is possible
MyBrainGotTLE
that's the question
there is a 50% chance of getting O(1) solution i mean correct in first case
and 50% chance are og fetting O(n!) solution whcich will take n! attempts
You should consider the worst case such as you are so unlucky that after a very large number (infinity) amount of attempts the array is still not sorted
The only guaranteed possible case is len(array) = 1
Counting sort with unordered_map takes O(n) time
i guess we are not using counting sort here
Also, by the way, it'd be $$$O(n+m\log{m})$$$, where $$$m$$$ is the number of distinct elements. An
unordered_mapis, as its name suggests, unordered. You can't iterate through it in sorted order.You forgot that there can be duplicating orders so worst case should be O(infinity)
if we think array have duplicating order
and one more fact is accotding to post array shoul dbe of 2 element
then array would be
array[n] == array[n+1]
and array[n+1] == array[n]
so it is already sorted and we are talking about unsorted arrays
No i meant when we random, there is a chance that we will get results we have already obtained before
LOL. First, you said that your input has only 2 elements. After that you said that your input has $$$n$$$ elements (refer to what you wrote in your big O notation). FYI, $$$n$$$ represents an arbitrarily large integer. It is not a fixed value.
So, given $$$n$$$ integers, Is your algorithm still $$$O(1)$$$? Obviously not, because your algorithm only works for $$$n=2$$$ (and it is not deterministic but that is besides the point).
i have realised that where was i getting wrong and i fixed this part in my blog as consclusion
Thank you for your precious time
A decision tree for comparisons is a binary tree with at least n! leaves. The height of a binary tree with L leaves is at least log2(L)
So, minimum number of comparisons in the worst case:
Comparisons = log_2(n!)
Using Stirling’s approximation:
log2(n!) = θ(log2(n))
Thus, any comparison-based sorting algorithm has worst-case time complexity:
Ω(nlogn)
Other methods like Frequency based sorting algorithms need to maintain frequency for each element in the array, so even being generous they are at least O(n)
Thanks, this was a really clear explanation! I now understand that in the general case, sorting can't be done in O(1) time because comparison-based algorithms need at least Ω(n log n) comparisons due to the number of possible permutations (n!), and even non-comparison ones like counting sort still require O(n) time to read the input.
I was initially thinking in terms of small, fixed-size arrays and randomness, but I realize now that doesn't count as a general solution.