2. Analyzing Time Complexities

Data Structures

1. Array

Operation	Average case	Worst case	Amortized
Insert	O(n)	O(n)	O(n)
Delete	O(n)	O(n)	O(n)
Access	O(1)	O(1)	O(1)

2. Linked List

Operation	Average case	Worst case	Amortized
Insert	O(1)	O(1)	-
Delete	O(1)	O(1)	-
Access	O(n)	O(n)	-

3. Heap

Operation	Average case	Worst case	Amortized
Insert	O(log n)	O(log n)	O(log n)
Delete	O(log n)	O(log n)	O(log n)
Heapify	O(n)	O(n)	O(n)
Access largest/smallest	O(1)	O(1)	O(1)

4. Hash Table

Operation	Average case	Worst case	Amortized
Insertion	O(1)	O(n)	-
Deletion	O(n)	O(n)	-
Access	O(1)	O(1)	-

5. Binary search tree

Operation	Average case	Worst case	Amortized
Insert	O(logn)	O(n)	-
Delete	O(logn)	O(n)	-
Access	O(logn)	O(n)	-

Algorithms

1. Sorting

Algorithm	Best case	Average case	Worst case	Amortized
Bubble sort	O(n)	-	O(n^2)	-
Quick sort	O(nlogn)	-	O(n^2)	-
Insertion sort	O(n)	-	O(n^2)	-
Merge sort	O(nlogn)	-	O(nlogn)	-
Heap sort	O(nlogn)	-	O(nlogn)	-

2. Searching

Algorithm	Best case	Average case	Worst case	Amortized
Linear	O(1)	-	O(n)	-
Binary	O(1)	-	O(logn)	-