please answer the blanks. and give me the answers as soon as possible. thank you
ID: 3591491 • Letter: P
Question
please answer the blanks. and give me the answers as soon as possible. thank you
3. Fill in the blanks Amortized Analvsis 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 50 100 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 ot computation In the worst case, a red-black tree insertion requires In the worst case a red-black tree deletion requires Walking a red-black tree with n nodes in pre-order takes Given a red-black tree with n elements, how fast can you sort them using the tree? a. rotations? b. node re-colorings? c. time? d. 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 ( ) while the actual time of a single X operation could be as low as ( ) and as high as ( )Explanation / Answer
a) In the worst case, a red black tree insertion requires ---- rotations?
answer: O(1). , atmost two rotations are performed.
b) In the worst case, a red black tree deletion requires ---- node re-colorings?
answer: (log n)
c) Walking a red-black tree with n nodes in pre-order takes---- time?
answer: (n) times.
d)Given a red-black tree with n elements, how fast can you sort them using the tree?
answer: Using the in-order traversal, (n)
e)How fast can we build a red-black tree with n elements?
answer: to insert n elements, O(n log n)times.
f)O(nlogn) time in the worst case, then the amortized time of an X operation is (log n),
while the actual time of a single X operation could b as low as (1) and as high as (n log n).
//for any clarification, please do comments.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.