Answer Happy

1. (28 points) Consider these time complexities:
O(n2),
O(nlgn), O(n),
O(lgn), and O(1). Give the time
complexity for each of the following operations. The “improved
select algorithm” refers to the select algorithm that uses the
technique of median-of-medians.
1). Average-case bucket sorting assuming keys are uniformly
distributed. _______
2). Worst-case bucket sorting assuming insertion sort is used
for elements in a bucket when necessary. ______
3). Worst-case finding the median using the improved select
algorithm. ______
4). Worst-case finding the ith largest element using
the improved select algorithm. ______
5). Best-case finding the median using the improved select
algorithm. ______
6). Best-case finding the ith largest element using the
improved select algorithm. ______
7). The best-case search operation in a skip list. _____
8). The average-case search operation in a skip list assuming a
proper randomization technique is used to construct the skip list.
_____
9). The DSW algorithm. _____
10). The best-case search operation in a red-black tree.
_____
11). The worst-case search operation in a red-black tree.
_____
12). Red-black tree insertion fixup procedure. _____
13). Best-case interval tree search. _____
14). Worst-case interval tree search. _____