Prof. Stewart Weiss Spring 2018 CSci335 Software Design and Analysis III Eram 1A

Question

Prof. Stewart Weiss Spring 2018 CSci335 Software Design and Analysis III Eram 1A Name: Answer all questions in the space profided. Usothe backs of the sheets for scratch work. 1" (12%) True or False? Circle T if the statement is true and F if it is not true. In the worst case, the number of steps in a remove operation in a binary search tree with n nodes is proportional to n. The internal path length of a binary tree of height h must be less than the internal path length of a binary tree of heighth+ 1. For all functions f, g, and h, if log2(n) E6(logs(n)). T F T F T T T F F f(n)60(g(n)) and g(n) E (h(n)) then f(n) o(h(n)). e F If every node whose depth is d has heigh t h in a binary tree, then the tree has height h 2, (6%) Give an example of a function f(n) s uol

Explanation / Answer

2^n = theta(3^n).
This is false because, 2^n is O(3^n), but not Omega(3^n)
A relation f(n) is in theta(g(n)), only if f(n) is in both omega(g(n)), and O(g(n)).

In the worst case, the number of steps in a remove operation in a binary search tree with
n nodes is proportional to n.
This is true, because in the worst case, to remove a node, it has to be attached to the
bottom most of the tree.

The internal path length of a binary tree of height h must be less than the internal path
length of a binary tree of height h+1.
The maximum internal path length of a binary tree of height h is always less than the maximum
internal path length of a binary tree of height h+1.
But when compared with path lengths other than the maximum, it may not be true.
So, the answer is False.

For all functions f, g, and h, if f(n) is O(g(n)), and g(n) is Omega(h(n)), then f(n) is O(h(n)).
If f(n) is O(g(n)), and g(n) is O(h(n)), then O(f(n)) is O(h(n)).
So, the answer is False.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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