1. Consider the follow ing function for reversing the elements of a list: def re

Question

1. Consider the follow ing function for reversing the elements of a list: def reverseClat s- Seack for x in 1nt s push (x) while rlst.appendC.pop)) return rlat What is the runtime complexity of the function when passed a list of length N? (b) O(log N) (c) O(N) d) On2) 2. Instead of using linked lists to handle collisions, as in the hashtable implementation presented in class, array-backed lists could be used to store key/value pairs for buckets-furthermore, if sorted by key, binary search could be used to locate an entry after hashing a key to a given bucket. What is the runtime complexity of a lookup (--gotitem) operation on a hashtable imple- mented in this way, containing N keys? (b) O(log N) (c) O(N) (d) O(N log N) 3. What is the runtime complexity of locating the largest value in an unbalanced binary search tree containing N elements? (b) O(log N) (c) O(N) (d) O(N log N)

Explanation / Answer

1.

Option c

2.

Runtime complexity of a lookup operation on a hashtable implemented in this way, containing N keys is O(N).

Option c

3.

Runtime complexity of locating the largest value in an unbalanced binary search tree containing N elements.

Option c

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.