Data Structures and Algorithms (DSA) in

Python
1. Introduction to DSA
Definition: Data Structures and Algorithms (DSA) is a fundamental field in computer science that
deals with the organization and storage of data in a way that allows efficient access and
modification (Data Structures), and a set of instructions or rules that define how to solve a
particular problem (Algorithms). Mastering DSA is crucial for writing efficient and optimized
code.

2. Basic Python Data Structures

2.1. Lists (Arrays)

Definition: Lists are ordered, mutable (changeable) sequences of items. They can store elements
of different data types and are one of the most versatile data structures in Python.

Example:

# Creating a list
my_list = [1, 2, 3, "hello", True]
print("Initial list:", my_list)

# Accessing elements
print("First element:", my_list[0])
print("Last element:", my_list[-1])

# Modifying elements
my_list[1] = 10
print("Modified list:", my_list)

# Adding elements
my_list.append(4) # Adds to the end
my_list.insert(1, "new") # Inserts at a specific index
print("After adding elements:", my_list)

# Removing elements
my_list.remove("hello") # Removes first occurrence of value
my_list.pop() # Removes and returns the last element
print("After removing elements:", my_list)

# Slicing
sub_list = my_list[1:4]
print("Sliced list:", sub_list)

# List Comprehensions
squares = [x**2 for x in range(5)]
print("Squares using list comprehension:", squares)

2.2. Tuples

Definition: Tuples are ordered, immutable (unchangeable) sequences of items. Once a tuple is
created, its elements cannot be modified, added, or removed. They are often used for fixed
collections of items or as keys in dictionaries.

Example:

# Creating a tuple
my_tuple = (1, 2, 3, "world")
print("Initial tuple:", my_tuple)

# Accessing elements (same as lists)

print("First element:", my_tuple[0])

# Tuples are immutable - uncommenting the line below will raise an error
# my_tuple[0] = 10

# Tuples can contain mutable elements (e.g., lists), but the tuple itself is
immutable
nested_tuple = (1, [2, 3], 4)
nested_tuple[1].append(5) # This is allowed
print("Tuple with mutable element modified:", nested_tuple)

# Unpacking tuples
a, b, c, d = my_tuple
print(f"Unpacked values: {a}, {b}, {c}, {d}")

2.3. Dictionaries (Hash Maps/Tables)

Definition: Dictionaries are unordered collections of key-value pairs. Each key must be unique
and immutable (e.g., strings, numbers, tuples), while values can be of any data type and are
mutable. Dictionaries provide efficient lookups, insertions, and deletions based on keys.

Example:

# Creating a dictionary
my_dict = {"name": "Alice", "age": 30, "city": "New York"}
print("Initial dictionary:", my_dict)

# Accessing values
print("Name:", my_dict["name"])
print("Age (using .get()):", my_dict.get("age")) # Safer access, returns None
if key not found

# Modifying values
my_dict["age"] = 31
print("Modified age:", my_dict)

# Adding new key-value pairs

my_dict["occupation"] = "Engineer"
print("After adding occupation:", my_dict)

# Removing elements
my_dict.pop("city") # Removes item with specified key
print("After removing city:", my_dict)

# Iterating through a dictionary

print("Keys:")
for key in my_dict.keys():
print(key)

print("Values:")
for value in my_dict.values():
print(value)

print("Key-Value Pairs:")
for key, value in my_dict.items():
print(f"{key}: {value}")

2.4. Sets

Definition: Sets are unordered collections of unique elements. They are mutable and do not allow
duplicate values. Sets are useful for performing mathematical set operations like union,
intersection, difference, and checking for membership.

Example:

# Creating a set
my_set = {1, 2, 3, 2, 4} # Duplicates are automatically removed
print("Initial set:", my_set)

# Adding elements
my_set.add(5)
my_set.add(1) # Adding existing element has no effect
print("After adding elements:", my_set)

# Removing elements
my_set.remove(3) # Raises KeyError if element not found
my_set.discard(6) # Does not raise error if element not found
print("After removing elements:", my_set)

# Set operations
set_a = {1, 2, 3, 4}
set_b = {3, 4, 5, 6}
print("Union:", set_a.union(set_b))
print("Intersection:", set_a.intersection(set_b))
print("Difference (A - B):", set_a.difference(set_b))
print("Symmetric Difference (A XOR B):", set_a.symmetric_difference(set_b))

# Checking for membership

print("Is 2 in set_a?", 2 in set_a)

3. Abstract Data Types (ADTs) & Their Implementations

3.1. Stacks

Definition: A stack is a linear data structure that follows the Last-In, First-Out (LIFO) principle.
Think of a stack of plates: you can only add or remove a plate from the top. The primary operations
are push (add an element) and pop (remove the top element).

Example:

# Implementing a stack using a Python list

stack = []

# Push operation
[Link](10)
[Link](20)
[Link](30)
print("Stack after pushes:", stack)

# Peek (view top element without removing)

if stack:
print("Top element (peek):", stack[-1])

# Pop operation
popped_item = [Link]()
print("Popped item:", popped_item)
print("Stack after pop:", stack)

popped_item = [Link]()
print("Popped item:", popped_item)
print("Stack after pop:", stack)

# Check if stack is empty

print("Is stack empty?", not bool(stack))

3.2. Queues

Definition: A queue is a linear data structure that follows the First-In, First-Out (FIFO) principle.
Think of a line at a supermarket: the first person in line is the first one to be served. The primary
operations are enqueue (add an element to the rear) and dequeue (remove an element from the
front).

Example:

from collections import deque

# Implementing a queue using [Link] (efficient for both ends)

queue = deque()

# Enqueue operation
[Link](10)
[Link](20)
[Link](30)
print("Queue after enqueues:", queue)

# Peek (view front element without removing)

if queue:
print("Front element (peek):", queue[0])

# Dequeue operation
dequeued_item = [Link]() # Removes from the left (front)
print("Dequeued item:", dequeued_item)
print("Queue after dequeue:", queue)

dequeued_item = [Link]()
print("Dequeued item:", dequeued_item)
print("Queue after dequeue:", queue)

# Check if queue is empty

print("Is queue empty?", not bool(queue))

3.3. Heaps (Priority Queues)

Definition: A heap is a specialized tree-based data structure that satisfies the heap property: for a
min-heap, the value of each node is less than or equal to the value of its children; for a max-heap,
the value of each node is greater than or equal to the value of its children. Heaps are typically used
to implement priority queues, where elements are retrieved based on their priority. Python's heapq
module implements a min-heap.

Example:

import heapq

# Creating a min-heap
min_heap = []

# Pushing elements onto the heap

[Link](min_heap, 3)
[Link](min_heap, 1)
[Link](min_heap, 4)
[Link](min_heap, 2)
print("Min-heap after pushes:", min_heap) # Note: internal representation
might not look sorted

# Popping the smallest element

smallest = [Link](min_heap)
print("Smallest element popped:", smallest)
print("Min-heap after pop:", min_heap)

# Getting the smallest element without popping (peek)

if min_heap:
print("Current smallest element:", min_heap[0])

# Example of a max-heap (by storing negative values)

max_heap = []
[Link](max_heap, -3)
[Link](max_heap, -1)
[Link](max_heap, -4)
[Link](max_heap, -2)
print("Max-heap (internal, using negative values):", max_heap)
largest = -[Link](max_heap)
print("Largest element popped (from max-heap):", largest)

3.4. Linked Lists

Definition: A linked list is a linear data structure where elements (nodes) are not stored at
contiguous memory locations. Each node contains data and a reference (or pointer) to the next
node in the sequence. Linked lists are dynamic in size and allow efficient insertions and deletions
compared to arrays, but random access is not efficient.

Example (Singly Linked List):

class Node:
def __init__(self, data):
[Link] = data
[Link] = None # Reference to the next node

class LinkedList:
def __init__(self):
[Link] = None # Head of the linked list

def append(self, data):

new_node = Node(data)
if not [Link]:
[Link] = new_node
return
last_node = [Link]
while last_node.next:
last_node = last_node.next
last_node.next = new_node
 def display(self):
current = [Link]
elements = []
while current:
[Link]([Link])
current = [Link]
print("Linked List:", " -> ".join(map(str, elements)))

def insert_at_beginning(self, data):

new_node = Node(data)
new_node.next = [Link]
[Link] = new_node

def delete_node(self, key):

current = [Link]
if current and [Link] == key:
[Link] = [Link]
current = None
return

prev = None
while current and [Link] != key:
prev = current
current = [Link]

if not current:
print(f"{key} not found in the list.")
return

[Link] = [Link]
current = None

# Usage
my_linked_list = LinkedList()
my_linked_list.append(1)
my_linked_list.append(2)
my_linked_list.append(3)
my_linked_list.display()

my_linked_list.insert_at_beginning(0)
my_linked_list.display()

my_linked_list.delete_node(2)
my_linked_list.display()

my_linked_list.delete_node(5)

3.5. Trees

Definition: A tree is a non-linear, hierarchical data structure consisting of nodes connected by

edges. Each tree has a root node, and each node can have zero or more child nodes. Trees are
widely used to represent hierarchical relationships, e.g., file systems, organization charts.
Example (Binary Tree - simplified):

class TreeNode:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None

# Creating a simple binary tree

root = TreeNode(1)
[Link] = TreeNode(2)
[Link] = TreeNode(3)
[Link] = TreeNode(4)
[Link] = TreeNode(5)

# Example of a simple in-order traversal

def inorder_traversal(node):
if node:
inorder_traversal([Link])
print([Link], end=" ")
inorder_traversal([Link])

print("In-order traversal:")
inorder_traversal(root)
print() # for newline

3.6. Graphs

Definition: A graph is a non-linear data structure consisting of a set of vertices (nodes) and a set
of edges that connect these vertices. Graphs are used to model relationships between objects, e.g.,
social networks, road maps.

Example (Adjacency List Representation):

Python
# Representing a graph using an adjacency list (dictionary in Python)
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"]
}

print("Graph (Adjacency List):", graph)

# Adding an edge
graph["A"].append("D")
graph["D"].append("A") # For an undirected graph, add to both
print("Graph after adding edge A-D:", graph)
# Simple traversal (e.g., checking neighbors)
print("Neighbors of B:", graph["B"])

4. Algorithms
4.1. Sorting Algorithms

Definition: Sorting algorithms are procedures that put elements of a list in a certain order (e.g.,
numerical or alphabetical). Python's built-in sort() method and sorted() function use Timsort,
which is a highly optimized hybrid algorithm.

Example (Python's built-in sort):

my_list = [64, 25, 12, 22, 11]

print("Original list:", my_list)

# Using list's sort() method (in-place sort)

my_list.sort()
print("Sorted list (using .sort()):", my_list)

my_list_2 = [64, 25, 12, 22, 11]

# Using sorted() function (returns a new sorted list)
new_sorted_list = sorted(my_list_2)
print("Original list 2:", my_list_2)
print("New sorted list (using sorted()):", new_sorted_list)

# Sorting in descending order

my_list.sort(reverse=True)
print("Sorted list (descending):", my_list)

Example (Bubble Sort - for illustration of a simple sorting algorithm):

def bubble_sort(arr):
n = len(arr)
for i in range(n):
# Last i elements are already in place
for j in range(0, n-i-1):
# Traverse the array from 0 to n-i-1
# Swap if the element found is greater than the next element
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr

arr = [64, 34, 25, 12, 22, 11, 90]

print("Original array for Bubble Sort:", arr)
print("Sorted array (Bubble Sort):", bubble_sort(arr))

4.2. Searching Algorithms

Definition: Searching algorithms are used to find a specific element within a data structure.
4.2.1. Linear Search

Definition: Linear search sequentially checks each element in the list until a match is found or the
end of the list is reached. It is simple but inefficient for large datasets.

Example:

def linear_search(arr, target):

for i in range(len(arr)):
if arr[i] == target:
return i # Return the index if found
return -1 # Return -1 if not found

my_list = [10, 20, 30, 40, 50]

target_1 = 30
target_2 = 60

print(f"Linear search for {target_1}: Index {linear_search(my_list,

target_1)}")
print(f"Linear search for {target_2}: Index {linear_search(my_list,
target_2)}")

4.2.2. Binary Search

Definition: Binary search is an efficient algorithm for finding an element in a sorted list. It works
by repeatedly dividing the search interval in half.

Example:

def binary_search(arr, target):

low = 0
high = len(arr) - 1

while low <= high:

mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else: # arr[mid] > target
high = mid - 1
return -1

sorted_list = [10, 20, 30, 40, 50, 60, 70]

target_1 = 50
target_2 = 25

print(f"Binary search for {target_1}: Index {binary_search(sorted_list,

target_1)}")
print(f"Binary search for {target_2}: Index {binary_search(sorted_list,
target_2)}")
4.3. Recursion

Definition: Recursion is a programming technique where a function calls itself, either directly or
indirectly, to solve a problem. It's often used for problems that can be broken down into smaller,
similar subproblems. A recursive function must have a base case to prevent infinite recursion.

Example (Factorial Calculation):

def factorial(n):
# Base case: if n is 0 or 1, factorial is 1
if n == 0 or n == 1:
return 1
# Recursive case: n * factorial of (n-1)
else:
return n * factorial(n - 1)

print("Factorial of 5:", factorial(5)) # Output: 120 (5 * 4 * 3 * 2 * 1)

print("Factorial of 0:", factorial(0)) # Output: 1

4.4. Dynamic Programming (DP)

Definition: Dynamic Programming is an algorithmic technique for solving complex problems by

breaking them down into simpler, overlapping sub-problems. It typically stores the results of sub-
problems to avoid redundant computations, leading to more efficient solutions than naive
recursion. This is often achieved through memoization (top-down) or tabulation (bottom-up).

Example (Fibonacci Sequence with Memoization):

# Using a dictionary for memoization

memo = {}

def fibonacci_dp(n):
if n in memo:
return memo[n]
if n <= 1:
return n
else:
result = fibonacci_dp(n - 1) + fibonacci_dp(n - 2)
memo[n] = result # Store the result
return result

print("Fibonacci(10) with DP:", fibonacci_dp(10)) # Output: 55

print("Memoization table:", memo)
4.5. Graph Algorithms

Definition: Graph algorithms are used to solve problems on graphs, such as finding the shortest
path between two nodes, determining connectivity, or traversing the graph.

4.5.1. Breadth-First Search (BFS)

Definition: BFS is a graph traversal algorithm that explores all the neighbor nodes at the present
depth before moving on to nodes at the next depth level. It uses a queue data structure.

Example:

from collections import deque

def bfs(graph, start_node):

visited = set()
queue = deque([start_node])
[Link](start_node)

traversal_order = []

while queue:
current_node = [Link]()
traversal_order.append(current_node)

for neighbor in graph[current_node]:

if neighbor not in visited:
[Link](neighbor)
[Link](neighbor)
return traversal_order

graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"]
}

print("BFS traversal starting from 'A':", bfs(graph, "A")) # Output: ['A',

'B', 'C', 'D', 'E', 'F']

4.5.2. Depth-First Search (DFS)

Definition: DFS is a graph traversal algorithm that explores as far as possible along each branch
before backtracking. It uses a stack (or recursion, which uses the call stack).
Example:

def dfs(graph, start_node, visited=None):

if visited is None:
visited = set()
[Link](start_node)
print(start_node, end=" ") # Process the node

for neighbor in graph[start_node]:

if neighbor not in visited:
dfs(graph, neighbor, visited)

graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"]
}

print("DFS traversal starting from 'A':")

dfs(graph, "A") # Output: A B D E F C
print() # for newline

4.6. Bit Manipulation

Definition: Bit manipulation involves performing operations directly on the individual bits of a
number. This can be used for optimizing certain algorithms, saving space, and solving problems
involving subsets or flags.

Example:

# Check if a number is even or odd using bitwise AND

def is_even_odd(n):
if (n & 1) == 0:
return "Even"
else:
return "Odd"

print("7 is:", is_even_odd(7)) # Output: Odd

print("10 is:", is_even_odd(10)) # Output: Even

# Setting a bit (making the nth bit 1)

def set_bit(n, pos):
return n | (1 << pos)

# Clearing a bit (making the nth bit 0)

def clear_bit(n, pos):
return n & ~(1 << pos)

# Toggling a bit (flipping 0 to 1, or 1 to 0)

def toggle_bit(n, pos):
return n ^ (1 << pos)

num = 5 # Binary: 0101

print(f"Original number: {num} (binary: {bin(num)})")

# Set 0th bit (rightmost)

num_set = set_bit(num, 0)
print(f"After setting 0th bit: {num_set} (binary: {bin(num_set)})") # 0101 ->
0101 (no change)

# Set 1st bit

num_set = set_bit(num, 1)
print(f"After setting 1st bit: {num_set} (binary: {bin(num_set)})") # 0101 ->
0111 (7)

# Clear 2nd bit

num_clear = clear_bit(num, 2)
print(f"After clearing 2nd bit: {num_clear} (binary: {bin(num_clear)})") #
0101 -> 0001 (1)

# Toggle 0th bit

num_toggle = toggle_bit(num, 0)
print(f"After toggling 0th bit: {num_toggle} (binary: {bin(num_toggle)})") #
0101 -> 0100 (4)

Core Concepts of Data Structures and

Algorithms (DSA)
Understanding the efficiency of algorithms is paramount in competitive programming and
software development. We use specific metrics to measure how well an algorithm performs,
particularly as the input size grows.

1. Time Complexity
Definition: Time complexity quantifies the amount of time an algorithm takes to run as a function
of the input size (usually denoted as 'n'). It doesn't measure the actual time in seconds (which can
vary based on hardware, programming language, etc.), but rather the number of operations or steps
an algorithm performs. We express time complexity using Big O notation, which describes the
upper bound or worst-case scenario for the growth rate of an algorithm's running time.
Why Big O Notation?

 Machine Independence: It provides a way to describe algorithm performance that is independent

of the specific machine or programming language.
 Scalability: It focuses on how the algorithm scales with larger inputs, which is critical for real-
world applications.
 Worst-Case Analysis: It typically describes the worst-case performance, ensuring that the
algorithm will perform at least as well as the Big O bound.

Common Time Complexities (from best to worst):

1.1. O(1) - Constant Time

Definition: The algorithm takes a constant amount of time to execute, regardless of the input size.
The number of operations does not change with 'n'.

Example:

def get_first_element(arr):
# Accessing an element by index is a constant time operation
if arr:
return arr[0]
return None

my_list = [10, 20, 30, 40, 50]

print(get_first_element(my_list))
# This function will always take one step (checking if arr is empty)
# and one more step (accessing arr[0]) regardless of how big `my_list` is.

1.2. O(log n) - Logarithmic Time

Definition: The time taken grows logarithmically with the input size. This usually occurs in
algorithms that divide the problem into smaller subproblems in each step (e.g., binary search). If
you double the input size, the time taken increases by only a constant amount.

Example:

def binary_search_complexity(arr, target):

# Assumes arr is sorted
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
 return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1

# For an array of size 16, it takes at most log2(16) = 4 comparisons.

# Each time, the search space is halved.

1.3. O(n) - Linear Time

Definition: The time taken grows linearly with the input size. If you double the input size, the time
taken approximately doubles.

Example:

def linear_search_complexity(arr, target):

for i in range(len(arr)): # Iterates through each element once
if arr[i] == target:
return i
return -1

# The number of operations is directly proportional to the size of `arr`.

# If `arr` has 10 elements, it might take up to 10 comparisons.
# If `arr` has 100 elements, it might take up to 100 comparisons.

1.4. O(n log n) - Linearithmic Time

Definition: The time taken grows proportionally to n multiplied by log n. This is common in
efficient sorting algorithms (e.g., Merge Sort, Timsort).

Example:

# Python's built-in sort is O(n log n)

my_list = [5, 2, 8, 1, 9, 4]
my_list.sort() # O(n log n) operation
print(my_list)

# While we don't implement Merge Sort here, its complexity is O(n log n)
# because it divides the array (log n) and then merges linearly (n).

1.5. O(n^2) - Quadratic Time

Definition: The time taken grows proportionally to the square of the input size. This often occurs
in algorithms with nested loops where each loop iterates through the input.
Example:

def bubble_sort_complexity(arr):
n = len(arr)
for i in range(n): # Outer loop runs n times
for j in range(0, n-i-1): # Inner loop runs roughly n times
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr

# For an array of size 10, it performs approximately 10*10 = 100 operations.

# For an array of size 100, it performs approximately 100*100 = 10,000
operations.

1.6. O(2^n) - Exponential Time

Definition: The time taken doubles with each addition to the input size. These algorithms are
usually unfeasible for even moderately sized inputs. Often seen in brute-force solutions to
problems like the traveling salesman problem or recursive Fibonacci without memoization.

Example:

def fibonacci_recursive_exponential(n):
if n <= 1:
return n
else:
# This will recalculate fibonacci_recursive_exponential(n-2) multiple
times
return fibonacci_recursive_exponential(n-1) +
fibonacci_recursive_exponential(n-2)

# fibonacci_recursive_exponential(5) will call fib(4) and fib(3)

# fib(4) will call fib(3) and fib(2)
# fib(3) will call fib(2) and fib(1)
# ...leading to many redundant calculations.
print("Fibonacci(5) (Exponential):", fibonacci_recursive_exponential(5))
# Try fibonacci_recursive_exponential(30) to feel the pain.

1.7. O(n!) - Factorial Time

Definition: The time taken grows extremely rapidly, proportional to the factorial of the input size.
These algorithms are practically impossible for even small inputs. Often seen in algorithms that
generate all permutations of a set.

Example:

import itertools
def generate_permutations(arr):
# [Link] generates all n! permutations
return list([Link](arr))

# For arr of size 3: 3! = 6 permutations

# For arr of size 10: 10! = 3,628,800 permutations (already very large)
# For arr of size 20: 20! is a massive number, computations become
impractical.
print("Permutations of [1, 2, 3]:", generate_permutations([1, 2, 3]))

2. Space Complexity
Definition: Space complexity quantifies the amount of memory (or auxiliary space) an algorithm
needs to run as a function of the input size 'n'. Similar to time complexity, it's also expressed
using Big O notation, focusing on the worst-case scenario.

Types of Space Complexity:

 Auxiliary Space: The extra space used by the algorithm beyond the input data. This is what we
typically focus on when talking about space complexity in competitive programming.
 Total Space: The sum of auxiliary space and the space taken by the input itself.

Common Space Complexities:

2.1. O(1) - Constant Space

Definition: The algorithm uses a constant amount of extra memory, regardless of the input size.

Example:

def sum_two_numbers(a, b):

# Only stores `a`, `b`, and `result` variables, which is constant.
result = a + b
return result

# No additional data structures are created that scale with input.

2.2. O(log n) - Logarithmic Space

Definition: The memory usage grows logarithmically with the input size. This can occur in
recursive algorithms where the depth of the recursion stack is logarithmic (e.g., binary search
recursion).
Example:

def binary_search_recursive_space(arr, target, low, high):

if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive_space(arr, target, mid + 1, high)
else:
return binary_search_recursive_space(arr, target, low, mid - 1)

# The depth of the recursion stack is logarithmic to the input size.

2.3. O(n) - Linear Space

Definition: The memory usage grows linearly with the input size. This is very common when an
algorithm needs to store a copy of the input, use an auxiliary array/list, or a hash map whose size
depends on 'n'.

Example:

def create_copy(arr):
# Creates a new list that is a copy of the input list.
new_list = list(arr)
return new_list

# The `new_list` takes memory proportional to the size of `arr`.

2.4. O(n^2) - Quadratic Space

Definition: The memory usage grows proportionally to the square of the input size. This often
occurs when storing a 2D matrix or graph adjacency matrix where the number of nodes is 'n'.

Example:

def create_adjacency_matrix(num_vertices):
# For a graph with 'num_vertices', an adjacency matrix of size
num_vertices * num_vertices
# will be created.
matrix = [[0] * num_vertices for _ in range(num_vertices)]
return matrix

# If num_vertices = 10, matrix size = 10x10 = 100 cells.

# If num_vertices = 100, matrix size = 100x100 = 10,000 cells.
3. Best, Average, and Worst-Case Analysis
When analyzing algorithms, especially sorting and searching, we often consider three scenarios:

 Best-Case: The minimum time/space an algorithm will take. For example, in linear search, if the
target element is the first element, it's the best case (O(1)).
 Average-Case: The expected time/space an algorithm will take for a typical input. This is often
harder to calculate precisely.
 Worst-Case: The maximum time/space an algorithm will take. This is the most important for
competitive programming as it guarantees the algorithm will perform within this bound even
under the most challenging input. Big O notation typically refers to the worst-case.

4. Time-Space Trade-off
Definition: A time-space trade-off is a common concept in algorithm design where you can often
reduce the time complexity of an algorithm by using more space, or vice-versa.

Example:

 Memoization/Dynamic Programming: By storing previously computed results (using extra space,

often O(n) or O(n^2)), we can significantly reduce the time complexity (e.g., from O(2^n) to O(n)
for Fibonacci).
 Hash Tables: They offer O(1) average time complexity for insertions, deletions, and lookups but
require O(n) space to store the key-value pairs. If you use a simple array for storage, search time
might be O(n) but space is O(1) if you don't grow it.

Choosing the right algorithm often involves balancing these two factors based on the problem
constraints. If memory is very limited, you might opt for a slower algorithm that uses less space.
If speed is critical, you might accept higher memory usage.