Suppose we have a recursive function defined on a binary tree. The function takes as input a node in the tree, calls another function bar that performs some work on the node and then makes recursive calls to itself on the left and right subtrees provided they are not empty.

def foo(u):

bar(u)

if u.left is not empty then

foo(u.left)

if u.right is not empty then

foo(u.right)

Suppose bar(u) takes O(|subtree(u)|) time to execute, where |subtree(u)| is the size of the subtree rooted at u. What is the time complexity of running foo from the root a tree with n nodes. Select the tightest bound that holds.

Question

Suppose we have a recursive function defined on a binary tree. The function takes as input a node in the tree, calls another function bar that performs some work on the node and then makes recursive calls to itself on the left and right subtrees provided they are not empty.

def foo(u):

bar(u)

if u.left is not empty then

foo(u.left)

if u.right is not empty then

foo(u.right)

Suppose bar(u) takes O(|subtree(u)|) time to execute, where |subtree(u)| is the size of the subtree rooted at u. What is the time complexity of running foo from the root a tree with n nodes. Select the tightest bound that holds.

BlackTom AI · Accepted Answer

Each call bar(u) costs Θ(|subtree(u)|), so the total running time is the sum of subtree sizes over all nodes: T(n) = Σ_{u in tree} Θ(|subtree(u)|).

Relevant concepts:
- |subtree(u)| = number of descendants of u (including u).
- Summing subtree sizes double-counts ancestor-descendant pairs: Σ_{u}|subtree(u)| = number of ordered pairs (ancestor, descendant).
- Worst-case trees can maximize this sum (a path/chain); balanced trees give smaller sums but we must give a bound that holds in general.

Step-by-step reasoning and intermediate calculations:
1. Write the total cost exactly (up to constants):
   T(n) = c · Σ_{u}|subtree(u)| for some constant c.
2. Interpret Σ_{u}|subtree(u)| as counting pairs (u, v) where v is in u’s subtree.
   So Σ_{u}|subtree(u)| = number of (ancestor, descendant) pairs.
3. Count pairs by fixing the descendant v: each node v has at most n ancestors (including itself), so
   Σ_{u}|subtree(u)| = Σ_{v}(number of ancestors of v) ≤ Σ_{v} n = n · n = n^2.
   Thus T(n) = O(n^2).
4. Show a matching lower bound (worst-case example): for a chain (a root with a single child, and so on),
   subtree sizes are n, n-1, n-2, ..., 1. Sum = n + (n-1) + ... + 1 = n(n+1)/2 = Θ(n^2).
   Therefore the bound O(n^2) is tight in the worst case (Θ(n^2)).

Why the correct answer is O(n^2):
- The total cost is the sum of all subtree sizes, which in the worst case equals n(n+1)/2, i.e., Θ(n^2). So O(n^2) correctly captures the worst-case running time.

Why other common bounds are incorrect:
- O(n) or O(n log n): too small, violated by the chain example which gives Θ(n^2).
- O(n^3): true but not tight; O(n^2) is the tightest simple asymptotic upper bound.

Conclusion: The running time is O(n^2), which matches the provided answer O(n2).

类似问题

What is the big-O of the worst-case time cost of inserting an element somewhere into an array of size n? Select the tightest bound that holds.

Which of the following is a big-O description that applies to the function g(n) = 18log n + 2n + 3n log n? Select the tightest bound that holds.

What is the time complexity of the following Python code? A = np.zeros(5) n = np.size(A) for i in range(n): A[i] = A[i]2 print(A) for j in range(i,n): for k in range(i,j): A[j] = A[i]/5 for i in range(n): print(A) A[i] = A[i]2 for j in range(i, n): A[j] = A[i]/5

What is the time complexity of the following Python code? A = np.zeros(5) n = np.size(A) for i in range(n): A[i] = A[i]**2 for j in range(i, n): A[j] = A[i]/5 print(A)

What is the time complexity of the following Python code? A = np.zeros(5) n = np.size(A) for i in range(n): A[i] = A[i]**2 for j in range(n): A[j] = A[i]/5

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单