Olympiad Programming 1

Lesson 02: Algorithm Analysis for Olympiad Programming

Learning Objectives

 Understand the concept of algorithm analysis.

 Learn how to evaluate the time and space complexity of algorithms.
 Apply these concepts to optimize solutions for Olympiad programming problems.

Lesson Content

1. Introduction to Algorithm Analysis

Algorithm analysis involves evaluating the efficiency of an algorithm, primarily in terms of time and
space complexity.

 Time Complexity: Measures the amount of time an algorithm takes to complete as a function of
the size of the input.
 Space Complexity: Measures the amount of memory an algorithm uses as a function of the size
of the input.

2. Big O Notation

Big O notation is used to describe the upper bound of an algorithm's running time or space
requirements, providing an asymptotic analysis of the algorithm's performance.

 O(1): Constant time

 O(log n): Logarithmic time
 O(n): Linear time
 O(n log n): Linearithmic time
 O(n2): Quadratic time
 O(2n): Exponential time

Phạm Văn Tú 1|
 Olympiad Programming 2

3. Analyzing Time Complexity

a. Constant Time Complexity - O(1)

An operation is said to have constant time complexity if it takes the same amount of time regardless of
the input size.

Example 0:

def get_first_element(arr):
return arr[0]

Example 1: Accessing an element in an array by index.

def get_element(arr, index):

return arr[index]

Example 2: Checking if a number is even or odd.

def is_even(n):
return n % 2 == 0

Example 3: Swapping two variables.

def swap(a, b):

temp = a
a = b
b = temp

b. Linear Time Complexity - O(n)

An operation is said to have linear time complexity if the running time increases linearly with the input
size.

Example 0:

def linear_search(arr, target):

for element in arr:
if element == target:
return True
return False

Example 1: Finding the maximum element in an array.

def find_max(arr):
max_element = arr[0]
for element in arr:
if element > max_element:
max_element = element
return max_element

Example 2: Calculating the sum of elements in an array.

def sum_array(arr):
total = 0
for element in arr:
total += element

Phạm Văn Tú 2|
 Olympiad Programming 3

return total

Example 3: Counting the number of occurrences of a specific element in an array.

def count_occurrences(arr, target):

count = 0
for element in arr:
if element == target:
count += 1
return count

c. Quadratic Time Complexity - O(n^2)

An operation is said to have quadratic time complexity if the running time increases quadratically with
the input size.

Example 0:

def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]

Example 1: Selection sort algorithm.

def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]

Example 2: Checking if a list has any duplicate elements (naive approach).

def has_duplicates(arr):
n = len(arr)
for i in range(n):
for j in range(i + 1, n):
if arr[i] == arr[j]:
return True
return False

Example 3: Multiplying two matrices.

def multiply_matrices(A, B):

n = len(A)
result = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
for k in range(n):
result[i][j] += A[i][k] * B[k][j]
return result

4. Analyzing Space Complexity

Phạm Văn Tú 3|
 Olympiad Programming 4

a. Constant Space Complexity - O(1)

An algorithm uses constant space if its memory usage does not grow with the input size.

Example 0:

def swap(a, b):

temp = a
a = b
b = temp

Example 1: Checking if a number is prime.

def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True

Example 2: Finding the maximum of two numbers.

def find_max(a, b):

if a > b:
return a
else:
return b

Example 3: Swapping the values of two variables.

def swap(a, b):

temp = a
a = b
b = temp

b. Linear Space Complexity - O(n)

An algorithm uses linear space if its memory usage grows linearly with the input size.

Example 0:

def create_list(n):
return [i for i in range(n)]

Example 1: Creating a list of the first n Fibonacci numbers.

def fibonacci_list(n):
fibs = [0, 1]
for i in range(2, n):
fibs.append(fibs[-1] + fibs[-2])
return fibs

Example 2: Reversing a string by converting it to a list of characters.

def reverse_string(s):
char_list = list(s)
char_list.reverse()

Phạm Văn Tú 4|
 Olympiad Programming 5

return ''.join(char_list)

Example 3: Counting the frequency of elements in an array.

def count_frequencies(arr):
frequency = {}
for element in arr:
if element in frequency:
frequency[element] += 1
else:
frequency[element] = 1
return frequency

c. Quadratic Space Complexity - O(n^2)

Example 1: Generating a 2D matrix of size n x n with zeros.

def generate_zero_matrix(n):
matrix = [[0] * n for _ in range(n)]
return matrix

Example 2: Storing the result of multiplying two n x n matrices.

def multiply_matrices(A, B):

n = len(A)
result = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
for k in range(n):
result[i][j] += A[i][k] * B[k][j]
return result

Example 3: Finding all pairs of elements in an array (cartesian product).

def all_pairs(arr):
n = len(arr)
pairs = []
for i in range(n):
for j in range(n):
pairs.append((arr[i], arr[j]))
return pairs

5. Practice Problems

Problem 1: Analyzing a Search Algorithm

Problem Statement: Analyze the time and space complexity of a binary search algorithm.

Solution:

def binary_search(arr, target):

left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:

Phạm Văn Tú 5|
 Olympiad Programming 6

right = mid - 1
return -1

# Time Complexity: O(log n)

# Space Complexity: O(1)

Problem 2: Optimizing an Algorithm

Problem Statement: Optimize the bubble sort algorithm to improve its time complexity.

Solution:

def optimized_bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped:
break

# Time Complexity: O(n^2) in the worst case, but can be O(n) in the best case if
the array is already sorted.
# Space Complexity: O(1)

Problem 3: Space Complexity of a Recursive Algorithm

Problem Statement: Determine the space complexity of a recursive Fibonacci function.

Solution:

def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)

# Time Complexity: O(2^n)

# Space Complexity: O(n) due to the call stack

Conclusion

In this lesson, we covered the basics of algorithm analysis, including time and space complexity, and
how to use Big O notation to describe the efficiency of algorithms. We also applied these concepts to
analyze and optimize algorithms commonly used in Olympiad programming contests. Mastering
algorithm analysis is crucial for writing efficient code and performing well in competitive
programming.

Phạm Văn Tú 6|
 Olympiad Programming 7

EXERCISES

Here are 10 practice problems to help students analyze algorithm complexity, each with detailed
explanations.

Exercise 1: Sum of Array Elements

Problem Statement: Write a function to calculate the sum of all elements in an array.

Solution:

def sum_array(arr):
total = 0
for element in arr:
total += element
return total

Analysis:

 Time Complexity: __________________________________________________________

 Space Complexity: __________________________________________________________

Exercise 2: Factorial of a Number

Problem Statement: Write a function to compute the factorial of a number n.

Solution:

def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)

Analysis:

 Time Complexity: __________________________________________________________

 Space Complexity: __________________________________________________________

Exercise 3: Check for Duplicates

Problem Statement: Write a function to check if there are any duplicates in an array.

Solution:

def has_duplicates(arr):
seen = set()
for element in arr:
if element in seen:
return True
seen.add(element)
return False

Analysis:

Phạm Văn Tú 7|
 Olympiad Programming 8

 Time Complexity: __________________________________________________________

 Space Complexity: __________________________________________________________

Exercise 4: Find Maximum Element

Problem Statement: Write a function to find the maximum element in an array.

Solution:

def find_max(arr):
max_element = arr[0]
for element in arr:
if element > max_element:
max_element = element
return max_element

Analysis:

 Time Complexity: __________________________________________________________

 Space Complexity: __________________________________________________________

Exercise 5: Reverse a String

Problem Statement: Write a function to reverse a string.

Solution:

def reverse_string(s):
return s[::-1]

Analysis:

 Time Complexity: __________________________________________________________

 Space Complexity: __________________________________________________________

Exercise 6: Merge Two Sorted Arrays

Problem Statement: Write a function to merge two sorted arrays into one sorted array.

Solution:

def merge_sorted_arrays(arr1, arr2):

merged = []
i, j = 0, 0
while i < len(arr1) and j < len(arr2):
if arr1[i] < arr2[j]:
merged.append(arr1[i])
i += 1
else:
merged.append(arr2[j])
j += 1
merged.extend(arr1[i:])
merged.extend(arr2[j:])
return merged

Analysis:

Phạm Văn Tú 8|
 Olympiad Programming 9

 Time Complexity: __________________________________________________________

 Space Complexity: __________________________________________________________

Exercise 7: Compute Fibonacci Numbers (Iterative)

Problem Statement: Write a function to compute the n-th Fibonacci number iteratively.

Solution:

def fibonacci(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b

Analysis:

 Time Complexity: __________________________________________________________

 Space Complexity: __________________________________________________________

Exercise 8: Find the Middle Element of a Linked List

Problem Statement: Write a function to find the middle element of a singly linked list.

Solution:

class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

def find_middle(head):
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow.val

Analysis:

 Time Complexity: __________________________________________________________

 Space Complexity: __________________________________________________________

Exercise 9: Find Intersection of Two Arrays

Problem Statement: Write a function to find the intersection of two arrays.

Solution:

def intersection(arr1, arr2):

set1 = set(arr1)
set2 = set(arr2)
return list(set1.intersection(set2))

Phạm Văn Tú 9|
 Olympiad Programming 10

Analysis:

 Time Complexity: __________________________________________________________

 Space Complexity: __________________________________________________________

Exercise 10: Count Inversions in an Array

Problem Statement: Write a function to count the number of inversions in an array (an inversion is a
pair of elements where the first element is greater than the second element and appears before it).

Solution:

def count_inversions(arr):
def merge_sort(arr):
if len(arr) < 2:
return arr, 0
mid = len(arr) // 2
left, left_inv = merge_sort(arr[:mid])
right, right_inv = merge_sort(arr[mid:])
merged, split_inv = merge(left, right)
return merged, left_inv + right_inv + split_inv

def merge(left, right):

i = j = 0
merged = []
inversions = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
inversions += len(left) - i
merged.extend(left[i:])
merged.extend(right[j:])
return merged, inversions

_, total_inversions = merge_sort(arr)
return total_inversions

Analysis:

 Time Complexity: __________________________________________________________

 Space Complexity: __________________________________________________________

These exercises provide hands-on practice for students to analyze and understand the complexities of
different algorithms, helping them develop the skills needed to optimize their solutions for competitive
programming and real-world applications.

Phạm Văn Tú 10 |