C++ Big-O time analysis? I\'ve been told to do \"Big-O time analysis\" for the f
ID: 3837370 • Letter: C
Question
C++ Big-O time analysis?
I've been told to do "Big-O time analysis" for the following functions and justify each of the answers:
bool bag::erase_one(const value_type& target){
node *target_ptr;
target_ptr = list_search(head_ptr, target);
if (target_ptr == NULL){
return false; // target isn’t in the bag, so no work to do
}
target_ptr->set_data( head_ptr->data( ) );
list_head_remove(head_ptr);
--many_nodes;
return true;
}
void bag::insert(const value_type& entry){
list_head_insert(head_ptr, entry);
++many_nodes;
}
Explanation / Answer
1)
bool bag::erase_one(const value_type& target){
node *target_ptr;
target_ptr = list_search(head_ptr, target);
if (target_ptr == NULL){
return false; // target isn’t in the bag, so no work to do
}
target_ptr->set_data( head_ptr->data( ) );
list_head_remove(head_ptr);
--many_nodes;
return true;
}
-->Analysis :
In this function list_search is called and it is done in linear order i.e seatch in linked list is done in linear order, if target element found the it return . So complexity of function is same as complexity of list_search and is equl to O(n) …(n is total element in list)
2)
void bag::insert(const value_type& entry){
list_head_insert(head_ptr, entry);
++many_nodes;
}
-->Analysis:
This function insert the element at head so there is no traversal of list. So complexity would be O(1)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.