COMP 210 - Help for MDTM 2

What is the worst-case complexity of a search in a BST with N elements?

• O(log N) - elements cannot be inserted in a sorted order, which makes it non-linear

• O(N) - elements can be inserted in a sorted order, which makes it linear

• O(1) - elements can be inserted in a sorted order, which makes it deal with constant time

• O(N^2) - elements cannot be inserted in a sorted order, which results in dealing with quadratic time.

What is the worst-case complexity of a search in a balanced BST with N elements?

• O(log N) - It would be a binary search with near equal numbers being eliminated and kept at each step

• O(log N) - it would not be a binary search with near equal numbers being eliminated and kept at each step

• O(N) - it would be a binary search with near equal numbers being eliminated and not kept at each step

• O(1) - it would not be a binary search, it would be constant

What is the worst-case complexity of a search in a Heap with N elements?

• O(N) - there is no other way to search for a specific element in a heap other than linear search

• O(1) - there is no other way to search for a specific element in a heap other than constant search

• O(log N) - there is no other way to search for a specific element in a heap other than logarithmic search

• O(N^2) - there is no other way to search for a specific element in a heap other than quadratic search

How many leaves are there in a perfect binary tree of height h?

• 2^h

• log base 2(h)

• h! * 2

Given that a heap has N elements and uses an ArrayList data structure, what is the average complexity of the above operation. Justify based on each of the steps involved in the dequeue operation.

• The average time complexity is O(log N). This is because dequeue has a step for each level of the tree the node must bubble down, possibly up to the entire height of the tree, or O(log N).

• The average time complexity is O(N). This is because dequeue has a step for each level of the tree the node must bubble down, possibly up to the entire height of the tree, or O(N).

• The average time complexity is O(1). This is because dequeue has a step for each level of the tree the node must bubble down, possibly up to the entire height of the tree, or O(1).

• The average time complexity is O(log N). This is because dequeue has a step for each level of the tree the node must bubble up, possibly up to the entire height of the tree, or O(log N).

Consider the following linked list implementation of a Queue class. Choose the code for the method 'Node<T> get(int i)' that returns the address of the i^th node (with i=0 being the node at the head of the queue), or returns a null if the i^th node does not exist.

• 
• 
• 

Consider the ArrayList implementation of a sorted List containing N items. What
would be the worst-case running time complexity, in Big-O notation, of the
following operations:

Inserting an item in the list (assuming the array does not have to be resized)?

• O(N)

• O(log N)

• O(1)

• O(N^2)

Consider the ArrayList implementation of a sorted List containing N items. What
would be the worst-case running time complexity, in Big-O notation, of the
following operations:

Searching for an item in the list?

• O(log N)

• O(N)

• O(1)

• O(N^2)

Retrieving the last item of the list?Consider the ArrayList implementation of a sorted List containing N items. What
would be the worst-case running time complexity, in Big-O notation, of the
following operations:

Retrieving the last item of the list?

• O(N)

• O(log N)

• O(1)

• O(N^2)

Consider the ArrayList implementation of a sorted List containing N items. What
would be the worst-case running time complexity, in Big-O notation, of the
following operations:

Consider the Queue ADT (Abstract Data Type), implemented as a Linked
List, what is the worst-case time complexity in Big-O notation of the Dequeue
operation? (You may assume the implementation has both the head and the
tail pointer.)

• O(1)

• O(N^2)

• O(log N)

• O(N)