1. (28 points) Consider these time complexities: O(n2), O(nlgn), O(n), O(lgn), and O(1). Give the time complexity for ea

[answerhappygod]

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. _____