Pick between these choices what the best answer is for the following questions:
ID: 3627614 • Letter: P
Question
Pick between these choices what the best answer is for the following questions:a. O(1)
b. O(log n)
c. O(n)
d. O(n log n)
e. O(n^2)
Consider each of the following problems as separate scenarios.
1. The time cost to sort n items using heapsort is:
2. The space time cost to store n items in a binary search tree is:
3. The time cost to add n elements to an initially empty singly-linked list by inserting at the front of the list is:
4. The time cost to add one element to an array containing n elements by inserting at the front of the array is:
5. The time cost to remove the smallest element from a min-heap containing n elements is:
6. The best-case time cost to find a data element in a linked list with n elements is:
7. The average case time cost to put a key-value pair in a hash table containing n entries is:
8. The worst case time cost to put a key-value pair in a hash table containing n entries is:
I would really appreciate a link or website in which I can refer to, to figure out how to answer these questions--especially for problems 7 and 8. I don't really know/understand how to figure out time or space costs for a hash table.
Explanation / Answer
1. The time cost to sort n items using heapsort is: O(n log n) 2. The space time cost to store n items in a binary search tree is: O(n log n) -- each element is stored in O(log n) time and we need to store n of them 3. The time cost to add n elements to an initially empty singly-linked list by inserting at the front of the list is: O(n) -- one operation to add each element = n operations 4. The time cost to add one element to an array containing n elements by inserting at the front of the array is: O(n) -- shift all n elements to the right and insert the new one 5. The time cost to remove the smallest element from a min-heap containing n elements is: O(log n) -- the heap is log n elements tall, because it's a binary tree, and we need to go from top to bottom to find the one we want 6. The best-case time cost to find a data element in a linked list with n elements is: O(n) -- search through each element in the list 7. The average case time cost to put a key-value pair in a hash table containing n entries is: O(1) -- it's constant time unless the table needs to be resized, in which case it's O(n) 8. The worst case time cost to put a key-value pair in a hash table containing n entries is: O(n) -- happens when the hash table needs to be resized, which occurs when there are n entries in an n-sized table With regards to 7 and 8, and an explanation of hash table resizing see here: http://stackoverflow.com/questions/3949217/time-complexity-of-hash-table http://stackoverflow.com/questions/2369467/why-are-hash-table-expansions-usually-done-by-doubling-the-size