#Big O Notation .sort (ArrayList)

1 messages · Page 1 of 1 (latest)

plush relic
#

Hey! Someone knows what's the big O notation for the method .sort used to sort a arraylist? Thanks 🙂

fair ventureBOT
#

<@&987246399047479336> please have a look, thanks.

#

Here is an AI assisted attempt to answer your question 🤖. Maybe it helps! In any case, a human is on the way 👍. To continue talking to the AI, you can use </chatgpt:1108714622413963314>.

#
TJ-Bot
Hey! Someone knows what's the big O notation for the method .sort used to sort a arraylist? Thanks 🙂

The Big O notation for the .sort() method used to sort an ArrayList in Java is O(n log n). This means that the time complexity of the sorting algorithm used by .sort() is proportional to n multiplied by the logarithm of n, where n represents the number of elements in the ArrayList. Overall, this indicates that as the size of the ArrayList increases, the time taken to sort it will increase at a slightly slower rate than a linear relationship.

It's important to note that different sorting algorithms may have different time complexities. The default sorting algorithm used by .sort() in Java is a variant of TimSort, which has an average time complexity of O(n log n) and a worst-case time complexity of O(n log^2 n).

Therefore, when using the .sort() method on an ArrayList in Java, you can generally expect it to have a time complexity of O(n log n), making it an efficient choice for sorting large collections of elements.

- AI generated response
molten laurel
scarlet yew
#

AI response was pretty on point too

modern dagger
#

the time taken to sort it will increase at a slightly slower rate than a linear relationship
doubt

#

it should be "faster rate"

#

otherwise it implies that the complexity is better than linear, which it's not

halcyon oxide
#

arraylists use TimSort so they're a standard O(n log n) sort

#

some array sorts are faster. byte[]'s sort uses counting sort if it's big enough, which is O(n)

amber aspen
#

also comparison based sorting algorithms can never be faster than O(n log n)

halcyon oxide
#

*in the worst case

#

They can be linear if everything is sorted already (or reversed, both handled in linear time by timsort)

amber aspen
#

Big O implies worst case

vivid parrot
#

its called Omega(n log n) btw, i.e. a lower bound. not an upper bound

halcyon oxide
halcyon oxide
amber aspen
vivid parrot
#

since f in O(n log n) means "f is faster/equals than n log n"

#

(in terms of asymptotic growth ofc)

amber aspen
#

should have said better rather than faster

vivid parrot
#

i want to avoid going into too much detail as this is alex thread and they are probably confused by all our "expert talk" anyways - after all they havent said a single thing since this thread started

molten laurel
#

Sort algo can never be faster than O(n), many are O(nlogn) or similar

static grotto
# amber aspen Big O implies worst case

for e.g. quicksort you can calculate the expected runtime which is asymptotic O(n log n) but the worst case is O(n^2) so just because you use the O notation that does not mean that is the worst case runtime

static grotto
#

also does anyone know why java uses timsort? Quicksort should be faster except the data is nearly sorted or am i wrong?

vivid parrot
#

big-O implies worst case. it has a "for all n" in it

#

when u read online about "but its worst case O(...)" then what these people actually do is not a general big-o analysis anymore but they restrict the input domain from "all inputs" to only the inputs that are bad for the algo. for example "all already sorted inputs are allowed now only" (what kind if input domain is the worst depends on the algo in question ofc). and then, after restricting the input domain they perform a big-o analysis

#

and that's what yields those statements

vivid parrot
vivid parrot
ripe socket
molten laurel
halcyon oxide
#

they do use quicksort (as a fallback) for primitive arrays

#

well, quicksort with insertion sort

#

There's been a lot of performance tuning in those sorting algorithms, so depending on the size of the input, the type of array etc, they will use different strategies

static grotto
# vivid parrot when u read online about "but its worst case O(...)" then what these people actu...

no but this is not the case for quicksort. e.g. randomised quicksort. you can say the runtime is a Random variable and then calculate the expected vaule of that depending on the input length. you could calulate that exact but since asymtotic is the standard you can estimate it upwards. and then you have E[runtime] <= c * n log n = O(n log n), because the probability for choosing always the largest or smallest element is so incredibly low, so the worst case is these one 0.000000000000000000...0001% probablity that for every partition the largest or smalles element was choosen as pivot. big O is a asymtotic notation you can e.g. say the expected (average) runtime of quicksort is in O(n log n) which makes sense for a las vegas algorithm like randomized quicksort

vivid parrot
#

we can continue this in #geek-speak in more detail if u want

#

lets wrap this thread up for now and leave it to alex to ask if there are any more questions