Data Structure and complexity analysis
computer science
Description
Data Structure and complexity analysis
Question 1 (15 marks) Short Answer (maximum 20 words):
Answer all five parts below.
Part A (3 marks): What is the worst case time complexity for binary search on a BST with n elements? Explain.
Part B (3 marks): The first time you run algorithm A on a dataset of n elements; it is faster than algorithm B. The second time you run algorithm A on a dataset of n elements; it is slower than algorithm B. Explain how this is possible. Give an example for algorithm A and algorithm B.
Part C (3 marks): If both have n nodes and are sorted smallest to largest, will it be faster to find the largest value in a sorted linked list or a minimum-level BST? Explain.
Part D (3 marks): What is the time complexity to delete the root of a minimum-level BST with nnodes? Explain.
Part E (3 marks): An implementation of quicksort has its worst case of O(n2) for an array in sorted order. Explain how this is possible/how this version of quicksort was implemented.
Page 2 of 5
Question 2 (10 marks) Complexity Analysis/Estimation:
Assume that an array has n random values. What is the time complexity of the following method that makes every element in the array equal to the largest element in the original array. Note: you must show all of your work to receive full credit.
public void makeLargest (int[] intArray)
{
int largest = intArray[0];
for (int i = 1; i < intArray.length; i++)
{
if (intArray[i] > largest)
{
largest = intArray[i];
for (int j = 0; j < i; j++)
intArray[j] = largest;
intArray[i] = largest;
}
public class BinNode
{
public char value;
public BinNode left;
public BinNode right;
}
public static int treeHeight (BinNode current)
{
} else
}
Page 3 of 5
Question 3 (10 marks) Recursion:
Write a recursive function that will calculate the height of a binary tree. root1
D B
AC
root2
Thus, the following statements would lead to the underlined output: Example 1:
System.out.println( treeHeight (root1) ); 3
Example 2:
System.out.println( treeHeight (root2) ); 1
Please write your method on the following page.
E
Note: root1 and root2 are instances of the class BinNode:
Page 4 of 5
