C++ List appropriate Worst Case Big O Notation under the different algorithms or
ID: 3842644 • Letter: C
Question
C++
List appropriate Worst Case Big O Notation under the different algorithms or data structure operations. Choose from right column and place under left column. Right column can be used more than once or not all. A. Empty () check method on Stack of 1000 elements with array as underlying data structure B. Traversing a Linked List from the Last Node to the Head Node C. Look Up of Node in a 100.000 element Binary Search Tree D. Traversing every node in Queue with array as underlying data structure E. Accessing key in 1.000.000 element Hash MapExplanation / Answer
A. Empty check method on Stack of 1000 elements.. O(1) , We just need to check for one elment. If one element is there which means it is not empty. If it is not there, it means Stack is empty.
B. Traversing a linked list from lastNode to the Head node: O(n), as linked list traversal is a sequential operation. We will start from the last node and move back to the previous node.. It means for N node, we need to do the operation N times. Hence O(N)
C. Lookup of Node in a 100,000 element BST: O(log n): As the Binary search trees are structured in proper format, they just take log n time to search amongst n nodes.
D. Traversiing Each node in the queue with array as underlying data structure: O(n), as queue traversal is a sequential operation, just similar to linked list.. We need to traverse each element once. Hence O(N)
E. Accessing Key in 1,000,000 element hashMap: O(1): As the hashmaps keys are stored at unique indices, it takes constant amount of time to get any key in the hashmap.. Hence O(1)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.