What is the worst-case big-oh time complexity of each of the following problems?
ID: 3816211 • Letter: W
Question
What is the worst-case big-oh time complexity of each of the following problems?
Given an integer list of length n, print the list in reverse order Given a queue containing q items (are represented as a circular list), and a stack containing s items (and represented as a linked list), remove the head of the queue and push it onto the stack. Given a tree of n notes as height h, turn the number of occurrences of a given object. Given a binary search tree of n nodes and height h, return the maximum value in the tree.Explanation / Answer
f) It does not matter we print array in forward/reverse direction, time complexity will be same.
code => for(int i =n-1;i>0;i++) print (array[i])
Worst case complexity: O(n)
g)Queue always maintains a head pointer and stack always maintain top pointer to push the element.
So it will happen in a constant time and not depends on number of elements in queue/stack.
Worst case complexity: O(1)
h)Need to access all the elements in order to count occurances of an object. All elements need to be traversed.
Worst Case complexity : O(n)
i)Maximum value of a binary tree can be obtained by recursively traversing right subtree of each node till we get a leaf. For balanced binary tree, worst case complexity will be O(h) because tree is balanced.
But in general without any conditions (unbalanced), worst case complexity is O(n)