Please answer the question using Big-O notation, and briefly explain the rationa
ID: 3748317 • Letter: P
Question
Please answer the question using Big-O notation, and briefly explain the rationale. Thank you so much!
1. What is the cost of finding the largest number in an unsorted list of n numbers? 2. What is the cost of finding the smallest element greater than 0 in a sorted list with n numbers. 3. What is the cost of finding the value associated with a key in a hash table with n numbers? (Assume the values and keys are both scalars.) 4. What is the cost of computing the inner product aTx, where a s d × 1 and x is d x 1? 5, what is the cost of computing the quadratic form xTAx when A is d × d and z is d × 1.Explanation / Answer
1. The cost of finding the largest number in an unsorted list is O(N) where N is the number of elements in the list.
Explanation: We can use Linear search to find the element. The pseudocode for linear search is given below.
Pseudocode: FUNCTION linearSearch(list):
FOR index FROM 0 -> length(list):
IF list[index] > max THEN
max = list[index]
ENDIF
ENDLOOP
RETURN max
Clear, the linear search algorithm will iterate the whole list and then return the max element. Hence, its complexity is O(N).
2. Cost: O(logN) where N is the number of elements
Explanation: We can use binary search to find the smallest element greater than 0. In this implementation, we will find the middle element and compare it with 0. If it is 0, we will search in the second hald, otherwise, we will search in the first half. We will return the mid element as along as we encounter an element which is not zero and its left is 0.
3. Cost: O(1)
Explanation: The cost of finding whether a key exists in the key or not in a hash table is O(1). Hence, we can just search the key in the hash table and it it exits, we can return its corresponding value.
4. Cost: O(d)
Explanation: In order to computet the inner product (dot product), we would have to iterate through all the d components in 'a' and 'x' and add their product.
NOTE: As per Chegg policy, I am allowed to answer only 4 questions on a single post. Kindly post the 5th question separately and I will try to answer it. Sorry for the inconvenience caused.