RUN TIME DIFFERENCE between using Integer and int in JAVA

help
, ,
1

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.
2

This might be useful to you to read:

:slight_smile:

Best,

Bruno

1 Like
3

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
4

  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.
5

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
6

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
7

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

8

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

thnxxx