Please give explanation why you chose your answer so I can compare with answer I
ID: 3802674 • Letter: P
Question
Please give explanation why you chose your answer so I can compare with answer I chose to see difference if there are any. Thanks will give good feedback
Question 8 1 pts Suppose that we want to implement the following data structure: the status of the structure is a set of pairs name, quantity) where name is a string with maximum length k (an integer constant) and quantity is a floating point number. The update operation is Transaction (name,amount); if before that operation the set does not contain a pair (name, something) then a pair (name,amount is inserted, but if such pair exists then it is replaced with (name,something amount). The query operation is Balance name), if the set contains a pair (name,something) it returns something, otherwise it returns 0. You can adapt one of the data structures that we have learned to implement a sequence of n updates and queries with as small expected running time as possible. This time is o O(n/log n) O(n logk n) O(n2) O(n) Question 9 1 pts Suppose that we want to implement a data structure with status and operations as before, but with an additional query High (name) which returns the highest value that could be returned by Balance(name) so far. E.g. in a sequence of operations Transaction (Piotr,3), Transaction (Piotr, 4), Transaction (Piotr,-5), High (Piotr), the last operation returns 7. Again, you can adapt data structures that we have learned so far to implement a sequence of n operation with as small expected running time as possible. This time is O(n log n O(n) O(n2) O O(n log n)Explanation / Answer
for question 8 the time complexcity will be O(n) while for qustion 9 the time complexcity will be O(nlogn).
Please let us know if you need further more details.