3. Fill in the blanks 50 100 Amortized Analysis is used for algorithms where an
ID: 3707861 • Letter: 3
Question
3. Fill in the blanks 50 100 Amortized Analysis is used for algorithms where an occasional operation is very slow, but most of the other operations are faster In Amortized Analysis we analyze a sequence of operations and guarantee a worst case-average time which is lower than the worst case time of a particular expensive operation. In computer science, amortized analysis is a method for analyzing a given algorithm's time complexity, or how much of a resource, especially time or memory, it takes to execute. 25 75 Asymptotic analysis is input bound i.e., if there's no input to the algorithm, it is concluded to work in a constant time. Other than the "input" all other factors are considered constant. Asymptotic analysis refers to computing the running time of any operation in mathematical units of computation. a. In the worst case, a red-black tree insertion requiresrotations? b. In the worst case a red-black tree deletion requires node re-colorings? c. Walking a red-black tree with n nodes in pre-order takestime? d. Given a red-black tree with n elements, how fast can you sort them using the tree? e. How fast can we build a red-black tree with n elements? f. If a data structure supports an operation X such that a sequence of n X's operations take: O (n log n) time in the worst case, then the amortized time of an X operation is O O while the actual time of a single X operation could be as low as ) and as high as o )Explanation / Answer
a). In worst case , red-black tree insertion requires at most 2 ( two ) rotations.
Answer : Two
b). In worst case, red-black tree deletion requires O( log N ) node re-colorings.
Answer : O( log N ) where N is the number of nodes in the tree.
c). Walking a red-black tree with n nodes in pre-order takes O(N) time.
Answer: O( N )
d). Given a red-black tree with n elements, how fast can you sort them using the tree ?
Answer: In O( n log n ) time
e). How fast can we build a red-black tree with n elements ?
Answer: In O ( n ) : Red black tree can be built recursively by placing middle element as root and the left and right halves of elements as their left and right subtrees respectively.
f). Actual time of a single operation can be as low as O ( n ) or linear time when log n = 0 which happens if n=1, and time can be as high as O( n^2 ) or quadriatic in some cases when the data structure is skewed ( not balanced ).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.