Part A (3 marks): What is the time complexity of the best case to insert a new n
ID: 3783708 • Letter: P
Question
Part A (3 marks): What is the time complexity of the best case to insert a new node into a minimum-level BST with n nodes? Explain. (Hint: You may draw a diagram as part of your solution.)
Part B (3 marks): The best case to find the smallest value in an unsorted array is O(1) – when there is only one element in the array. True or false? Explain.
Part C (3 marks): If both have n nodes and are sorted smallest to largest, will it be faster to find the smallest value in a sorted linked list or a minimum-level BST? Explain.
Part D (3 marks): Two O(n2 ) algorithms will always take the same amount of time for a given value of n. True or false? Explain.
Part E (3 marks): You have a (large) unsorted set of n records that you wish to store in a BST. The BST will be built by adding one record at a time. Will it be faster to build the BST if the records are first sorted so that they can be added to the BST in sorted order? Yes or no? Explain.
Explanation / Answer
Hi I have answered first 4 parts.
Please repost last part in separate post.
Please let me know in case of any issue.
Part A (3 marks): What is the time complexity of the best case to insert a new node into a minimum-level BST with n nodes? Explain. (Hint: You may draw a diagram as part of your solution.)
Since maximum height of minimum-level BST is logn.
So time complexity to insert a node is logn.
Part B (3 marks): The best case to find the smallest value in an unsorted array is O(1) – when there is only one element in the array. True or false? Explain.
True. It takes O(1) to get minimum from unsorted array if there is only one element.
If there are more than 1 elements in unsorted array, then to find minimum element, entire array has to be scan(linear search).
In this case it takes O(n) time.
Part C (3 marks): If both have n nodes and are sorted smallest to largest, will it be faster to find the smallest value in a sorted linked list or a minimum-level BST? Explain.
If linked list is sorted smallest to largest, then it takes O(1) time to find smallest value because first node will store the smallest value.
But to search smallest element in minimum-level BST it takes O(logn) time because left most node of tree stores smallest value.
Part D (3 marks): Two O(n2 ) algorithms will always take the same amount of time for a given value of n. True or false? Explain.
No, O(n2) is the Big-O notation and it is true for large value of n. For smaller value O(n2) can be faster than O(n) algorithms.