Data-Structures-and-Algorithms

Time Complexity

• O(n!): Factorial time complexity, represents the complexity of an algorithm where the time it takes to complete grows factorially with the input size n.

• O(1): Constant time complexity, operations that take the same time regardless of input size.

• O(n): Linear time complexity, operations that scale linearly with input size.

• O(n²): Quadratic time complexity, operations that involve nested iterations over input data.

• O(log n): Logarithmic time complexity, operations that reduce the problem size in each step.

• O(n log n): Log-linear time complexity, operations that divide the problem into smaller subproblems and process each independently.

Time Complexity of different Data Structures and Algorithms

---

Elementary Data Structures

1. Array

• Fixed Size
• Dynamic Size

2. Matrices

• Fixed Size
• Dynamic Size

3. Linked List

• Singly Linked List

1. With Both Head and Tail Pointers
   C++ code Python code
2. With Head Pointer only
   C++ code

• Doubly Linked List
  C++ code
• Circular Linked List

1. Using Singly
   C++ code

2. Using Doubly
   C++ code

3. Stack

• Using Fixed Sized Array
• Using Dynamic Array or Vector
• Using Linked Lists
  C++ code

5. Queue

• Using Fixed Sized Array
• Using Dynamic Array or Vector
• Using Linked Lists
  C++ code

6. Hash Table

• Hash Function
• Collision Handling

1. Open Addressing
2. Using Chaining
   C++ code

---

Basic Operations

Operation	Detail
Access	Retrieve an element from the data structure.
Insert	Add a new element into the data structure.
Delete	Remove an existing element from the data structure.
Update	Modify an element in the data structure.
Search	Locate an element by its value or key.
Traverse	Visit each element in the data structure, often used to perform operations on all elements.
Check	Determine certain properties or conditions, such as whether the structure is empty or whether an element exists.

Why Sorting is not mentioned in basic operations?

Sorting is typically not included as a fundamental operation for all data structures because:

Not All Data Structures Support Sorting Directly:
Some data structures, like stacks or queues, are inherently unordered and don't support direct sorting operations. Sorting is more relevant to data structures like arrays or lists, where elements have a specific order.

Sorting is an Operation on Data, Not a Data Structure:
Sorting is often considered an algorithmic operation applied to data structures rather than a fundamental operation of the data structures themselves. For example, you sort an array using sorting algorithms, but sorting isn't a built-in operation of the array data structure.

Sorting Complexity:
Sorting introduces complexity that depends on the type of data structure and the algorithm used. It's not a basic operation like access or insertion, which are more universally applicable.

Time Complexity of Basic Operations on Elementary Data Structures

Array

Operation	Time Complexity	Note
Access	O(1)	-
Insert	O(n)/O(1)	Inserting from an arbitrary position / Inserting at the end if there is space
Delete	O(n)/O(1)	deleting from an arbitrary position / deleting from the end
Update	O(1)	-
Search	O(n)/O(log n)	Linear search / Binary search if sorted

Matrix

Operation	Time Complexity	Note
Access	O(1)	-
Insert	O(m . n)	If resizing or modifying a specific element in a fixed-size matrix
Delete	O(m . n)	Similar to insert if resizing or modifying
Update	O(1)	-
Search	O(m . n) / O(log n)	Linear search / if sorted

Linked List

• With Head Pointer Only:

Operation	Time Complexity	Note
Access	O(n)	-
Insert	O(1)/O(n)	At the head / At an arbitrary position
Delete	O(1)/O(n)	At the head / At an arbitrary position
Update	O(n)	-
Search	O(n)	Linear search

• With Both Head and Tail Pointers:

Operation	Time Complexity	Note
Access	O(n)	-
Insert	O(1)/O(n)	At the head or tail / At an arbitrary position
Delete	O(1)/O(n)	At the head or tail / At an arbitrary position
Update	O(n)	-
Search	O(n)	Linear search

Stack

• Array:

Operation	Time Complexity	Note
Access	O(1)	-
Push	O(1)/O(n)	Fixed-sized or No resizing required / When resizing is required
Pop	O(1)	-
Update	O(1)	-
Search	O(n)	-

• Linked List:

Operation	Time Complexity	Note
Access	O(n)	-
Push	O(1)	At the Head
Pop	From the Head	-
Update	O(n)	-
Search	O(n)	-

Queue

• Array:

Operation	Time Complexity	Note
Access	O(1)	-
Enqueue	O(1)/O(n)	Fixed-sized or No resizing required / When resizing required
Dequeue	O(1)	-
Update	O(1)	-
Search	O(n)	-

• Linked List:

Operation	Time Complexity	Note
Access	O(n)	-
Enqueue	O(1)	At the Tail
Dequeue	O(1)	From the Head
Update	O(n)	-
Search	O(n)	-

Hash Table

Average case for all basic operations on hash table is O(1) and Worst case if there are many collisions in Open Addressing or all elements hash into the same bucket in Chaining is O(n).

---

Sorting Algorithms

Core Sorting Algorithms to Master

• Selection Sort
  Pseudocode C++ code Python code

• Bubble Sort
  Pseudocode C++ code Python code

• Insertion Sort
  Pseudocode C++ code Python Code

• Merge Sort
  Pseudocode C++ code Python Code

• HeapSort
  Pesudocode

• QuickSort
  Pseudocode

• Counting Sort
  Pseudocode

• Radix Sort
  Pseudocode

• Bucket Sort
  Pseudocode

• ShellSort
  Pseudocode

• TimSort
  Pseudocode

• 3-way Merge Sort
  Pseudocode

Time Complexities

Algorithm	Worst Case	Average Case
Selection Sort	O(n2)	O(n2)
Bubble Sort	O(n2)	O(n2)
Insertion Sort	O(n2)	O(n2)
Merge Sort	O(n log n)	O(n log n)
HeapSort	O(n log n)	O(n log n)
QuickSort	O(n2)	O(n log n)
Counting Sort	O(n + k)	O(n + k)
Radix Sort	O(nk)	O(nk)
Bucket Sort	O(n2)	O(n + k)
ShellSort	O(n2)	O(n log n) to O(n2)
TimSort	O(n log n)	O(n log n)
3-way Merge Sort	O(n log n)	O(n log n)

Less common but useful to know

• Comb Sort
• Tree Sort
• Odd-Even Sort / Brick Sort

---

Searching Algorithms

Core Searching Algorithms to Master

• Linear Search
• Binary Search
  Python Code
• Hashing

Less common but useful to know

• Interpolation Search
• Ternary Search
• Jump Search
• Exponential Search
• Fibonacci Search

---

Tree Data Structures

• Binary Tree
• Binary Search Tree
• Ternary Tree
• AVL Tree
• Red Black Tree
• Segment Tree
• N-ary Tree
• B-Tree

Tree Traversal

• Pre Order
• In Order
• Post Order