Match the questions with the correct Big O Notation. You may use an answer more
ID: 3836196 • Letter: M
Question
Match the questions with the correct Big O Notation. You may use an answer more than Once. Print all the nodes of a linked list Insert an item to the beginning of a linked list Heap sort, for array-based lists, is of the order ____ even in the worst case. The insertion sort algorithm is of the order of ______. In a binary search tree, the average number of nodes visited during a search is approximately ______. Union on an implicit set that is stored as a sorted list Addition to an explicit set Find an element in a balanced binary search tree that contains n elements. A. O (1) B. O (log_2n) C. O (n) D. O(nlog_2n) E. O(n^2)Explanation / Answer
1) To print all node, just traverse through the list and print the items. So it will take O(n)
2) create a new node and do new_node->next=head and head =new_node. Therefore it is O(1)
3) deletion in heap take O(logn) in worst case. delete min elemt in O(logn) and print them . There are n elemts. Therefore it is O(nlogn)
4) It has order O(n^2)
5) The average is height of the tree. The tree height can be O(n). So complexity is O(n)
6) finding the position where it should be inserted is O(n). But we have to move other elements to insert this. So it is O(n).
7) Directly add to end of the set. O(1).
8) Balanced binary search tree height is O(logn). Therefore finding an element is done in O(logn).