Suppose we have a recursive function defined on a 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 parent provided it has one.

def foo(u):

bar(u)

if u.parent is not empty then

foo(u.parent)

Suppose bar(u) takes O(1) time to execute. What is the time complexity of running foo from a leaf of a tree with n nodes. Select the tightest bound that holds.

Question

Suppose we have a recursive function defined on a 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 parent provided it has one.

def foo(u):

bar(u)

if u.parent is not empty then

foo(u.parent)

Suppose bar(u) takes O(1) time to execute. What is the time complexity of running foo from a leaf of a tree with n nodes. Select the tightest bound that holds.

BlackTom AI · Accepted Answer

Each recursive call processes exactly one node on the path from the starting leaf up to the root, and bar(u) costs O(1) per node.

1) Relevant concepts:
- Time per node: bar(u) = O(1).
- Number of calls: equals the number of nodes on the ancestor chain from the leaf to the root (call this h, the path length or height from that leaf).
- Big-O for worst-case trees: we want an upper bound that holds for any tree of n nodes.

2) Step-by-step reasoning:
- Let h be the number of nodes visited by foo when called on the leaf (including the leaf and root). Each visited node triggers one bar call and then possibly a recursive call to its parent, until the root is reached.
- Total work = sum of O(1) over the h visited nodes = O(h).

3) Intermediate calculation details:
- If each call costs at most c time units, total time = c · h.
- Since h is at most n (the longest possible ancestor chain in any n-node tree is n, e.g., a chain/linked-list shaped tree), we have total time ≤ c · n = O(n).
- In the worst case h = n, so time = Θ(n) for that worst-case tree. For other trees h may be smaller (e.g., balanced tree leaf-to-root path ≈ O(log n)), but the question asks for the tightest bound that always holds for an arbitrary n-node tree.

4) Why O(n) is correct:
- O(n) is a valid upper bound for all possible trees because h ≤ n always. It captures the worst-case linear-time behavior when the tree is a chain.
- It is the tightest general upper bound because no asymptotically smaller function (like O(log n) or O(1)) can bound the runtime for every n-node tree (chains defeat those).

5) Why other bounds are incorrect:
- O(1) or O(log n): too small, fail on chain-shaped trees where h = Θ(n).
- Θ(n): not valid as a tight two-sided bound for every tree because some trees produce much smaller runtimes (e.g., a star gives h = 2 → Θ(1)), so Θ(n) does not hold for all inputs.
- Larger bounds like O(n^2) are true but not tight.

6) Conclusion:
Therefore the tightest general upper bound that always holds for running foo from a leaf in an n-node tree is O(n), which matches the provided answer O(n).

类似问题

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搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单