Time limitation exceeded in Java compared to Python on the exact same code

Question

The following code I wrote in JAVA takes more than 2 seconds to execute in some absurd test cases:

import java.util.*;
public class Main
{
    public static void main(String args[])
{
    Scanner sc= new Scanner(System.in);
    int n= sc.nextLong();
    long a[]= new long[n];
    for(int i=0; i<n; i++)  // Input.
    {
        a[i]= sc.nextInt();
    }

    for(int i=0; i<n-1; i++)  // Sorting(descending order).
    {
        for(int j=0; j<n-i-1; j++)
        {
            if(a[j]<a[j+1])
            {
                long t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
            }
        }
    }

    int k=1;
    long max=a[0];

    while(k<=n-1)   // Comparing
    {
        long k1=a[k]*(k+1);
        
        if(max<k1)
        {
            max=k1;
        }

        k++;
    }

    System.out.println(max);
    sc.close();
}
}

But the same code written in Python takes less:

n=int(input())
l=[]
for i in range(0,n):
    l.append(int(input()))
l.sort(reverse=True)
k=1;
max=l[0]
while(k<n):
    k1=l[k]*(k+1)
    if(max<k1):
        max=k1
    k=k+1
print(max)

Why? Results after executing the JAVA code in CodeChef

I cannot review the Test cases which have failed.

This might be of use to you: https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java — Jeroen Steenbeeke, Jun 14 '21 at 07:12
Yes but you waste 32 bits space since it won't be utilized. Also, I am not sure what the loop in second half doing. — Yoshikage Kira, Jun 14 '21 at 07:17
@Goion http://codechef.com/LRNDSA01/problems/ZCO14003 This is the question, there is an execution time limit of 2 sec. — Leteps, Jun 14 '21 at 07:20
can you please add it in the question itself. It will definitely help all the users want to answer your question. — Yoshikage Kira, Jun 14 '21 at 07:21

Monsieur Merso · Accepted Answer · 2021-06-14T07:40:33.177

2

There is a difference in java and python implementations:
In java you wrote some kind of a bubble sort with complexity O(n^2), here it is:

   for(int i=0; i<n-1; i++)  // Sorting(descending order).
    {
        for(int j=0; j<n-i-1; j++)
        {
            if(a[j]<a[j+1])
            {
                long t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
            }
        }
    }

And in python you are using built-in sort method, which I think, has complexity of O(n*logn)

l.sort(reverse=True)

That is the reason for time difference. If you'll use Arrays.sort() in java, it probably will fix the problem.

edited Jun 14 '21 at 07:40

answered Jun 14 '21 at 07:16

Monsieur Merso

1,459
1
15
18

2

Just for info: Python sort uses TimSort and Java sort uses Dual-Pivot Quicksort – Yoshikage Kira Jun 14 '21 at 07:20
Another note: `Arrays.sort()` in Java can perform in O(n^2) in some cases. – Barish Namazov Jun 14 '21 at 07:52
Thanks it worked, I didn't realise that bubble sort was so damn slow. – Leteps Jun 14 '21 at 14:19

Time limitation exceeded in Java compared to Python on the exact same code

1 Answers1