What is the worst-case big-oh time complexity of each of the following problems?

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)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.