CODEWITHSUNDEEP
pythonalgorithmdata-structurestime-complexitycomplexity-theory
DoomLord
DoomLord

Reputation: 3

What will be the time complexity of the following program

Can anyone find the time complexity of the following python 3.6 program :

I tried to find and my answer is O(N*n), where N is the range of the very first loop and n is the range of the second for loop which is inside the first for loop

This program is for https://www.codechef.com/FEB20B/problems/SNUG_FIT problem on codechef.

N=int(input())
for _ in range(N):
    S=0
    n=int(input())
    A=list(map(int, input().split()))[:n] #Assume amount of inputs to be strictly of n numbers
    B=list(map(int, input().split()))[:n]
    A.sort();A.reverse()
    B.sort();B.reverse()

    for i in range(0,len(A)): # Here range is n (same as len(A))
        if A[i]>=B[i]:
            S=S+B[i]
        else:
            S=S+A[i]
    print(S)

Upvotes: 0

Views: 418

Answers (2)

Pritam Banerjee
Pritam Banerjee

Reputation: 18923

The for loop is O(N) and inside that you sort O(nlog(n)) so overall it becomes O(Nnlog(n)).

After that you have another for loop which runs O(n).

Now the overall time complexity looks like this:

O(N( nlogn + n)) which effectively is O(Nnlog(n))

Upvotes: 1

Faruk Hossain
Faruk Hossain

Reputation: 1203

@Pritam Banerjee wrote -

O(N( nlogn + n)) which effectively is O(Nlog(n))

Actually it is not true.

I am describing it more clearly along with the code.

N=int(input())
for _ in range(N):    # O(N)
    S=0
    n=int(input())
    # The following line is O(n)
    A=list(map(int, input().split()))[:n] #Assume amount of inputs to be strictly of n numbers
    # This line is also O(n)
    B=list(map(int, input().split()))[:n]
    A.sort();A.reverse()    # this is O(nlog(n))
    B.sort();B.reverse()    # this is also O(nlog(n))

    for i in range(0,len(A)): # Here range is n (same as len(A))  # this is O(n)
        if A[i]>=B[i]:
            S=S+B[i]
        else:
            S=S+A[i]
    print(S)

So overall O(N( n + n + nlog(n) + nlog(n) + n)

We can calculate in the following way - 

  O(N( n + n + nlog(n) + nlog(n) + n)
= O(N( 3n + 2nlog(n))
= O(N (n + nlog(n)) (we can eliminate const number when determining complexity)
= O(N(nlog(n)) (as n > nlog(n), so we can eliminate the small part)
= O(N*nlog(n))

So overall complexity is O(N*nlog(n), not O(Nlog(n).

There are more difference between O(N*nlog(n) and O(Nlog(n).

Hope this post will help you a lot.

Thanks.

Upvotes: 0

Related Questions