Here again is the non-member interleave function for Sequences from Sequence.cpp:

void interleave(const Sequence& seq1, const Sequence& seq2, Sequence& result) { Sequence res; int n1 = seq1.size(); int n2 = seq2.size(); int nmin = (n1 < n2 ? n1 : n2); int resultPos = 0; for (int k = 0; k < nmin; k++) { ItemType v; seq1.get(k, v); res.insert(resultPos, v); resultPos++; seq2.get(k, v); res.insert(resultPos, v); resultPos++; } const Sequence& s = (n1 > nmin ? seq1 : seq2); int n = (n1 > nmin ? n1 : n2); for (int k = nmin ; k < n; k++) { ItemType v; s.get(k, v); res.insert(resultPos, v); resultPos++; } result.swap(res); } 

Assume that seq1, seq2, and the old value of result each have N elements. In terms of the number of ItemType objects visited (in the linked list nodes) during the execution of this function, what is its time complexity? Why?

Here is an implementation of a related member function. The call

s3.interleave(s1,s2); 

sets s3 to the result of interleaving s1 and s2. The implementation is

void Sequence::interleave(const Sequence& seq1, const Sequence& seq2) { Sequence res; Node* p1 = seq1.m_head->m_next; Node* p2 = seq2.m_head->m_next; for ( ; p1 != seq1.m_head && p2 != seq2.m_head; p1 = p1->m_next, p2 = p2->m_next) { res.insertBefore(res.m_head, p1->m_value); res.insertBefore(res.m_head, p2->m_value); } Node* p = (p1 != seq1.m_head ? p1 : p2); Node* pend = (p1 != seq1.m_head ? seq1 : seq2).m_head; for ( ; p != pend; p = p->m_next) res.insertBefore(res.m_head, p->value); // Swap *this with res swap(res); // Old value of *this (now in res) is destroyed when function returns. } 

Assume that seq1, seq2, and the old value of *this each have about N elements. In terms of the number of ItemType objects visited during the execution of this function, what is its time complexity? Why? Is it the same, better, or worse, than the implementation in part a?