RUN TIME DIFFERENCE between using Integer and int in JAVA

In JAVA is there any difference in using Integer and int at run time ??


1.Integer n[] = new Integer[100000];
2.int n[]= new int[1000000];

on solving this question i got AC when i used Integer,but got TLE when i used int.My code for that problem is http://ideone.com/Iqq22S

plzz explain the difference of using them and why much time is taking while using primitive data type int.

This might be useful to you to read:

:slight_smile:

Best,

Bruno

1 Like

Really?

As I can see, there is a note:

Please be careful that answer might not fit in 32 bit data type.

Typically using Integer is slower comparing to int as far as I know. Please post submission links.

1 Like

When you use integer merge sort is used, while using int quick sort is used so an anti-quick sort input would lead to TLE.
http://codeforces.ru/blog/entry/2298

1 Like
  1. http://codeforces.com/contest/439/submission/6817912

  2. http://codeforces.com/contest/439/submission/6817926


    1 st one giving TLE and 2nd one giving AC.

I see now, the reason is in Arrays.sort(c); - when primitive types are used, quicksort is used, when Objects (like Integer) merge sort is used.

Codeforces, unfortunatelly, has anti quicksort inputs, I really hate this… If you want try to shuffle before sorting and you will see, but there is not easy (one liner) way how to do that in Java :frowning:

If you decide to do so, look at Fisher–Yates shuffle (this was in Google Code Jam 2014 also - here).

1 Like

@u_seem_surprsd is correct merge sort instead of heap sort - fixed

ok !! merge sort takes o(n*log n) for worst case but quicksort takes o(n^2) for worst case…

thnxxx