CMSC132 Exam 3 Runtimes and Formulas

No joke this is the 4th knowt set I've created in on week...should I get help? Also I may have done some things wrong so pls lmk if there are any mistakes.

Lookup and Insertion on an Unordered Linked List

n+1 = O(n)

Insertion on an Unordered Linked List

O(1)

Lookup and Deletion on an Unordered Linked List

n+1 = O(n)

Deletion on an Unordered Linked List

O(1)

Indexing on an Unordered Linked List

O(n)

Search or Lookup on a Balanced BST

O(log(n))

Search or Lookup on a Degenerate BST

O(n)

Lookup and Insertion on a Balanced BST

O(log(n))

Lookup and Insertion on a Degenerate BST

O(n)

Lookup and Deletion on a Balanced BST

O(log(n))

Lookup and Deletion on a Degenerate BST

O(n)

Number of Elements in a Perfect Binary Tree of Height h

2^(h+1)-1

Location Formula for Parent of i in a Binary Tree

floor((i-1)/2)

Location Formula for Left Child of i in a Binary Tree

2i+1

Location Formula for Right Child of i in a Binary Tree

2i+2

Height of Heap

O(log(n))

How much memory space will be used to store an undirected graph that has n vertices and m edges using an adjacency list?

O(m)

Min Heap Insertion

O(log(n))

Finding Maximum Element in Min Heap

O(n)

Lookup and Insertion on an Ordered Linked List

O(n)

Insertion on an Ordered Linked List

O(n)

Lookup and Deletion on an Ordered Linked List

O(n)

Deletion on an Ordered Linked List

O(n)