Microlink Information and Technology College
Department Of Computer Science
Introduction to Complexity Theory Group Assignment
Group Members
Name ID
Abenezer Mengistu 15,900/22
Daniel Tesfu 15,908/22
Ermiyas Abera 16,156/22
Gemechis Chala 16,701/22
Henok Emagnu 15,902/22
Leul Berhanu 16,165/22
Muluken Endale 16,700/22
Natnael Garomsa 16,111/22
Simaf Abdulkerim 15,816/22
Taye Birhanu 15,899/22
Submitted To: Mr. Tessema M.
Submission Date: FEB, 2024
Addis Ababa, Ethiopia
1. Explain merge sort with an example. Compute its time complexity.
Merge Sort is a divide-and-conquer sorting algorithm that splits an unsorted list into smaller
sublists, sorts them recursively, and merges them back into a single sorted list.
It efficiently sorts large datasets with O(n log n) time complexity (faster than simpler algorithms
like Bubble Sort’s O(n²)). It is stable (preserves order of equal elements) and ideal for linked lists
or external sorting.
The algorithm follows “Divide”, “Conquer”, and “Merge” workflow. It first divides the lists into
two groups and repeats it until it gets the groups (sublists) own 1 element. Then it compares
elements from each sublist and then picks the smaller one, and repeats until merged.
Example: Sorting an array [56, 124, 78, 12, 5, 4, 23]
Step 1: Divide the array into halves until subarrays have 1 element:
Array = [56, 124, 78, 12, 5, 4, 23]
[56, 124, 78] and [12, 5, 4, 23]
[56], [124, 78], [12, 5], [4, 23]
[56], [124], [78], [12], [5], [4], [23]
Step 2: Merge pairs while sorting
Merge [56] & [124] → [56, 124]
Merge [78] & [12] → [12, 78]
Merge [5] & [4] → [4, 5]
Merge [23] into [4, 5] → [4, 5, 23]
Merge [56, 124] & [12, 78] → [12, 56, 78, 124]
Final merge of [12, 56, 78, 124] & [4, 5, 23] → [4, 5, 12, 23, 56, 78, 124]
Merge sort has a time complexity of O(n log n) in all cases (best, average, and worst). The time
complexity can be computed as follows:
At each step, the array is split into two halves: T(n) = 2T(n/2) + O(n).
i.e 2T(n/2) = Time to sort two subarrays of size n/2.
O(n) = Time to merge two sorted subarrays.
Next it solves the Recurrence through levels (using the recursion tree method):
Level 1: 1 merge of size n → O(n)
Level 2: 2 merges of size n/2 → 2×O(n/2) = O(n)
Level 3: 4 merges of size n/4 → 4×O(n/4) = O(n)
Level 4: 8 merges of size n/8 → 8×O(n/8) = O(n)
The splitting stops at subarrays of size 1.
Total Levels = log₂n (since we divide by 2 each time).
Total Time = O(n) × log n = O(n log n).
i.e The logarithmic factor (log n) comes from the number of divisions, and the linear factor
(n) comes from merging at each level.
2. Define Big O notation.
Big O Notation is a mathematical concept used in computer science to describe the upper bound
of an algorithm's time or space complexity as a function of the input size n. It focuses on the
worst-case growth rate, helping to understand how an algorithm's resource requirements (like
runtime or memory) scale as the input size increases.
The following are some of its key Purposes
Compare Algorithm Efficiency: Developers can evaluate algorithms based on
scalability, independent of hardware or implementation.
For example: an O(nlog n)O(n \log n)O(nlogn) sorting algorithm (like merge sort) is
more efficient than an O(n2)O(n^2)O(n2) algorithm (like bubble sort) for large datasets.
Simplify Analysis: Big O abstracts away constants and lower-order terms to highlight the
dominant factor affecting growth.
For instance, the expression 5n2+12n+205n^2 + 12n + 205n2+12n+20 simplifies to
O(n2)O(n^2)O(n2).
Predict Scalability: It helps estimate an algorithm's performance as input sizes grow,
which is crucial for designing large-scale systems.
Examples of Big O Complexity
Complexity Example Algorithm Growth Rate
O(1) Accessing an array element Constant time
O(\log n) Binary search Logarithmic time
O(n) Linear search Linear time
O(n \log n) Merge sort, Quick sort Linearithmic time
O(n²) Bubble sort, nested loops Quadratic time
O(2^n) Naive Fibonacci, subset Exponential time (intractable)
generation
