□ Big-O

binary search tree is a sorted data structure

binary search ree is already sorted.

there will be no need to waste memory or processing time sorting records

Array

Insert = O(1) +(heap allocation overhead)

Search = O(n)

Delete = O(n)

Sorted Array

Insert = O(n)

Search = O(log n)

Delete = O(n)

Linked List

Insert = O(1)

Search = O(n)

Delete = O(n)/O(1)

Sorted List

Insert = O(n)

Search = O(n)

Delete = O(n)/O(1)

Balanced Binary Tree

Insert = O(logN)

Search = O(logN)

Delete = O(logN)

Hash Table (BST) - Using a 'good' hash function

Insert = O(1)

Search = O(1)

Delete = O(1)

http://www.csee.umbc.edu/courses/undergraduate/202/spring07/Lectures/ChangSynopses/modules/m33-big-O/slides.php?print

Big-O Notation

For functions f(n) and g(n), we say that "f(n) is Big-O of g(n)" if

There exists a constant c > 0 there exists a constant n₀ such that 
for all n ≥ n₀, 0 ≤ f(n) ≤ c * g(n)

We write f(n) = O(g(n)), but the "=" is not the usual meaning.

The intention is to allow us to say

• 3*n² + 14*n - 7 = O(n²)
• 0.0007 * n³ is not O(n²)

Technically, 10^1,000,000*n is O(n), but programs with that running time is still very slow. 

---

---

Arrays vs Linked Lists

Asymptotic running times for n items:

	Insert	Search	Delete*
Arrays	O(1)	O(n)	O(n)
Sorted Arrays	O(n)	O(log n)	O(n)
Linked Lists	O(1)	O(n)	O(n)/O(1)
Sorted Linked Lists	O(n)	O(n)	O(n)/O(1)

*Running time for deletion from a linked list depends on whether you already have a pointer for the node to be deleted. 

---

---

Arrays vs Linked Lists

Suppose we have n items inserted and do n searches:

• Arrays: n * O(1) + n * O(n) = O(n) + O(n²) = O(n²)

• Sorted Arrays: n * O(n) + n * O(log n) = O(n²) + O(n log n) = O(n²)

• Linked List: n * O(1) + n * O(n) = O(n) + O(n²) = O(n²)

• Sorted Linked List: n * O(n) + n * O(n) = O(n) + O(n²) = O(n²)

If we have all n items before hand, we can sort them all at the same time in O(n log n), plus n * O(log n) for n searches for O(n log n) time total.

If not, we need binary search trees. 

---

---

A Binary Search Tree

For each node in a binary search tree, its left child (if any) holds a smaller number and its right child (if any) holds a larger number. 

---

---

Balanced Binary Search Trees

There are several schemes for maintaining a O(log n) height for a binary search tree n nodes: AVL trees, Red-Black trees, B-trees, 2-3 trees, ...

For such trees:

• Insert: O(log n) time

• Find: O(log n) time

• Delete: O(log n) time

---

---

Hash Tables

• Stores items in an array.

• Uses a hash function to compute the array index of an item.

• Ideally the size of the array is close to the number of items.

• A collision occurs when the hash function assigns the same index to two items.

• Open hashing places items with the same index in a linked list.

• Closed hashing finds some other place in the array for the second item that has the same index.

---

---

Hash Tables

Using a "good" hash function:

• Insert: O(1) time (average)

• Find: O(1) time (average)

• Delete: O(1) time (average)

In the worst case, all items have the same hash index and a closed hash table degenerates into an unsorted array.

There are provably good hash functions.