Perform a Big (O) analysis of the overloaded + function for bag. Explain your an

Question

Perform a Big (O) analysis of the overloaded + function for bag. Explain your analysis.

bag operator +(const bag& b1, const bag& b2)

    {

            bag answer;

answer += b1;

            answer += b2;

            return answer;

    }

Given:

void bag::operator +=(const bag& addend)

    // Library facilities used: cstdlib, node1.h

    {

            node *copy_head_ptr;

            node *copy_tail_ptr;

            if (addend.many_nodes > 0)

            {

                list_copy(addend.head_ptr, copy_head_ptr, copy_tail_ptr);

                copy_tail_ptr->set_link( head_ptr );

                head_ptr = copy_head_ptr;

                many_nodes += addend.many_nodes;

            }

    }

Explanation / Answer

bag operator +(const bag& b1, const bag& b2)
{
bag answer;   //Just initializes an object answer.
       answer += b1;   //The method += overloading operator is called.
answer += b2;   //The method += overloading operator is called.
return answer;
}
And now, coming to += operator.
As there is a tail pointer to the list, an operation set_link(head_ptr) method is called,
to append b1 to answer. Then b2 is appended to the list.
Which means the method set_link() is called twice.
If set_link() is of efficiency O(1), then the efficiency of + overloading operator is still O(1).

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.