# Algorithms Summary Points – Part 6: Decision Tree, Bucket Sort, Radix Sort

This note has some summary points from my study of algorithms and algorithmic analysis. If you have little or no idea of the concepts I will talk about, this note may not be so helpful to you. I only post these here to serve as a quick note or as a refresher about these concepts should the need arise. In that case, I suggest you take an advanced course on algorithms and data structures first.  Nevertheless, if you are interested in discussing any of the concepts here I will be glad to be of help.

## Decision Tree, Bucket Sort, Radix Sort

The number of comparisons performed in order to arrive at an arrangement found in a leaf node equals the depth of that leaf node in the decision tree.

Number of comparisons performed in the worst case = the depth of the deepest node = height of the decision tree

For input size n, leaves L, height h, number of comparisons c,

• C = h (in the worst case) – this is for the longest path in the tree
• L = n!
• L ≤ 2h
• So, h >= ceil (log L)
• Which also means C >= ceil (log L)
• So, >= ceil (log n!)
• Which means C = Ω (log n!)
• And we know that log n! is in Ω (n log n)
• So, C = Ω (n log n)

### Bucket Sort

• Works using 1 bucket. The bucket is an array whose length m is the upper bound of the range of elements in the original array.
• Then it traverses the original array and increment the value in the bucket at the index equal to the value of the current element – Just like counting.
• When done, we traverse through the bucket and if the current element is >0, we insert into our output array, the index of the current element, the number of times it occurs.
• Running time: O(m + n). Where m is the size of the bucket and n is the size of the input