Perform a Big (O) analysis of the overloaded + function for bag. Explain your an
ID: 3816357 • Letter: P
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).
Simply speaking, the starting node of b1 is added to answer, which is of constant time, and b2 is again added to answer, which is also a constant time. So, the time required is constant.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.