Please answer in full detail. Consider the following line of codes find the over
ID: 3918269 • Letter: P
Question
Please answer in full detail.
Consider the following line of codes find the overall complexity -
struct node* current1 = lst1->firstLink->next;
struct node* current2 = lst2->firstLink->next;
int found =0;
while (current1 != lst1->lastlink)
{
while (current2 != lst2->lastlink)
{
if ( current1 ->value == current2 ->value)
found ++;
else
current2 = current2->next;
}
current2 = lst2->firstLink->next;
current1= current1->next;
}
O(logn)
O(n+1)
O(n)
O(n3)
None of the above
Explanation / Answer
The answer is None of the above.
There are two lists (say of length m(lst1) and n(lst2))
The program is checking the presence of each elemenet in the first list
in the second list.Whenever a match is found , the found variable gets
incremented.
As there are two while loops. The outer while loop is running for say m times
and the inner while loop is running for say n times.
The overall complexity should be m* n