can someone explain why 6-9 are those time complexities 6. Suppose we implemente
ID: 3606270 • Letter: C
Question
can someone explain why 6-9 are those time complexities
6. Suppose we implemented a set collection in a class named Arrayset that used an array as the storage data structure. Suppose also that we maintained the array in ascending natural order of its element.s. s Assurme that in the call s1.equals (s2) both sl and s2 are instances of the ArraySet clas each contain N elements. What is the best big-oh time complexity that the equals method coud 1 n f no class and achieve? o(N) c) O(N log N) (d) o(N2) . Suppose we implemented a set collection in a class named ArraySet that used an array as the storage data structure. Suppose also that we did not keep the elements of the array in any particular order Assume that in the call sl weersz path Tmd-s2 nrerrettmesortheAr ray set class and eacn contanclements. What is the best big-oh time complexity that the equals method could achieve? (a) o1) (b) O(N) et in order (c) O(N log N) 8. Suppose we implemented a set collection in a class named LinkedSet that used a singly-linked list of nodes as the storage data structure. Suppose also that we maintained the linked let in ascending natural order of its elements. Assume that in the call s1.equals (s2) both s1 and s2 are instances of the LinkedSet class and each contain N elements. What is the best big-oh time complexity that the equals method could achieve? (c) (d) O(NlogN) O(N2) 9. Suppose we implemented a set collection in a class named Linkedset that used a singly-linked list of nodes as the storage data structure. Suppose also that we did not keep the elements of the linked list in any particular order. Assume that in the call s1.equals (s2) both s1 and s2 are instances of the Linkedset class and each contain N elements. What is the best big-oh time complexity that the equals method could achieve? (b) O(N) O(N log N)Explanation / Answer
6) Here, we are using an array structure. Also, both instances (S1 & S2) are sorted in ascending order.
for operatioin S1.equals(S2) two cases are there:
1) S1.equals(S2) = true. In this since both array are sorted they will exactly look the same. Thus, we need to compare both elements index wise only. So toal comparision will be N.
2) S1.equals(S2) = false. In this suppose last element of the array is different then also we need maximum N comparision to find out where s1==s2 or not.
Following code will demostrate the algo:
flag = 0;
for(int i =0;i<N;++i ){
flag = 0;
if(S1[i]==S2[i]){
flag = 1;
}
if(flag==0){
printf("S1 not equal to S2");
break;
}
}
Clearly, we are running only one loop, maximum N times.
Therefore , Complexity = O(N).
9)Here we are using linked list. Also there is no particular order in which elements are present in the list.
List S1 and S2 are bot sorted here. So, we can not do index wise comparision. we have to go to each and every elemnt to compare whether they are matchin or not.
Following program demostarte it:
flag = 0;
for(int i=0;i<N;++i){
flag =0;
for(int j=0;j<N;++j){
if(S1[i]==S2[j]){
flag = 1;
}
}
if (flag == ){
printf("S1 not equal to S2");
break;
}
}
Since we are using two nested loops here each is running N time.
Therefore the complexity is O(N^2)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.