Python Forum
What is the run time complexity of this code and please explain? - Printable Version

+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: General Coding Help (https://python-forum.io/forum-8.html)
+--- Thread: What is the run time complexity of this code and please explain? (/thread-30792.html)



What is the run time complexity of this code and please explain? - samlee916 - Nov-05-2020

set1=set(input().split())#TAKING INPUT OF SETS
set2=set(input().split())
l=[]#CREATING EMPTY LIST FOR STORING THE COMMON DATA OF SETS
flag=0
#LOOP FOR CHECKING COMMON VALUE IN SETS 
for i in set1:
    for j in set2:
        if i==j:
            flag=1
            l.append(i)
if flag==0:#CHECKING FLAG VALUE IF IT IS ZERO THEN IT MEANS THERE IS NO COMMON DATA
    print("NULL")
l1=[]#LIST FOR STORING ALPHABATIC DATA
l2=[]#LIST FOR STORING NUMERIC DATA
#SEPARATING ALPHABATIC AND NUMERIC DATA
for i in l:
    i=str(i)
    if i.isalpha():
        l1.append(i)
    elif i.isdigit():
        l2.append(i)
l1=sorted(l1)#SORTING ALPHABATIC DATA
l2=sorted(l2)#SORTING NUMERIC DATA
s=''
#STORING THE ALPHABATIC AND NUMERIC DATA IN SINGLE VARIABLE
for i in l1:
    s=s+i
for j in l2:
    s=s+j
print(' '.join(s))#JOINING ALPHABATIC AND NUMERIC DATA



RE: What is the run time complexity of this code and please explain? - ibreeden - Nov-06-2020

What exactly is your question?


RE: What is the run time complexity of this code and please explain? - deanhystad - Nov-06-2020

What is the run time complexity of this code and please explain?

O(n^2). The code in lines 6-10 determine how many operations are required. If we assume len(set1) == len(set2) == N, then len(l) == N^2, and the length of list "l" controls how many times all the operations in lines 16-21 occur. There are a couple of sorts, but I am going to assume Python sort is better than O(n^2).

Even if one of the sets contained only 1 element I would still say the complexity is O(n^2) because of the sorts.