Suppose we have a balanced binary search tree $T$ holding $n$ numbers. We are given two numbers $L$…

Question

Suppose we have a balanced binary search tree $T$ holding $n$ numbers. We are given two numbers $L$ and $H$ and wish to sum up all the numbers in $T$ that lie between $L$ and $H$. Suppose there are $m$ such numbers in $T$. If the tightest upper bound on the time to compute the sum is $O(n^a\log^bn+m^c\log^dn)$, the value of $a+10b+100c+1000d$ is ______.

Accepted Answer

Correct answer: 110 — Answer: 110 Key idea: Find the first element in the range in O(log n), then visit the m in-range elements using in-order successor steps in O(m). This gives a total time of O(log n + m). Step 1: Search for L (or the smallest element ≥ L) in the balanced BST. This takes O(log n). Step 2: From that node, repeatedly move to the in-order successor to visit each of the m elements in the range. These successor steps cost O(1) amortized each, so total O(m). Translate to the given form O(n^a log^b n + m^c log^d n): choose a = 0, b = 1 (to get the log n term) and c = 1, d = 0 (to get the m term). Then compute a + 10b + 100c + 1000d = 0 + 10·1 + 100·1 + 1000·0 = 110.

Suppose we have a balanced binary search tree \(T\) holding \(n\) numbers. We…