Home Index

1. Algorithms

+ 1 Binary Search Tree

+ 2 Breadth First Search

+ 3 Depth First Search

+ Java

+ Python

Algorithms /

Big-O notation guarantees for the cost of insertion and deletion

Sorting Algorithms

1. Merge Sort: O(n log n)

Sort each pair of elements then, sort every four elements by merging every two pairs Then, sort every 8 elements, etc O(n log n) expected and worst case

2. Quick Sort: O(n log n) worst: O(n^2)

Pick a random element and partition the array, such that all numbers that are less than it come before all elements that are greater than it Then do that for each half, then each quar- ter, etc O(n log n) expected, O(n^2) worst case

3. Bucket Sort: O(n + m)

Partition the array into a finite number of buckets, and then sort each bucket individually. This gives a time of O(n + m), where n is the number of items and m is the number of distinct items

4. Selection Sort: O(n^2)

Find the smallest element using a linear scan and move it to the front Then, find the second smallest and move it, again doing a linear scan Continue doing this until all the elements are in place O(n^2)

5. Bubble Sort: O(n^2)

Start at the beginning of an array and swap the first two elements if the first is bigger than the second Go to the next pair, etc, continuously making sweeps of the array until sorted O(n^2)


Binary Search Tree: O(log n)

Binary search trees keep their keys in sorted order, so that lookup and other operations can use the principle of binary search

Breadth First Search

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores the neighbor nodes first, before moving to the next level neig