Question

Please compute the time complexity of the algorithm. (ex: O(N) or O(N log N))

void Set::unite(const Set& seti, const Set& set2) { const Set* sp = &set2; if (this == &seti) { if (this == &set2) return; } else if (this == &set2) sp = &setl; else { *this = seti; if (&setl == &set2) return; } Node* pl = m_head->m_next; Node* p 2 = sp->m_head->m_next; while (pl != m_head & & p2 != sp->m_head) { if (pl->m_value < p2->m_value) pl = pl->m_next; else { if (pl->m_value > p2->m_value) insertBefore(p1, p2->m_value); else pl = pl->m_next; p2 = p2->m_next; } } for ( ; p2 != sp->m_head; p2 = p2->m_next) insertBefore(m_head, p2->m_value); } Assume that seti, set2, and the old value of *this each have N elements. In terms of the number of linked list nodes visited during the execution of this function, what is its time complexity? Why?

Answer 1

Answer: O(N)

The first loop runs for N times since it runs till all elements of sp has been traversed and sp will only contain either set1 or set2 (from if else statements at top) and both have N elements.

The second loop also runs till all elements of sp has been traversed i.e. N times.

Thus complexity = O(N+N) = O(N)

Answer 2

The time complexity for the above code is O(N). The reason for the same is both the loops run N times only.