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