Data Structures and Algorithms
0. Introduction
Asymptotic notation (Big-O)
Worst-case asymptotic running time (“upper bound”)
It provides the upper limit on how the running time of an algorithm grows as the input size
increases
Suppress:
- Constant factors – too system-dependent
- Lower-order items – irrelevant for large inputs
T(n) = O(f(n)) if and only if there exists
positive constants c and n0 such that
T(n) <= c * f(n)
for all n > n0
Classes of algorithmic complexity
Growth rate Name Code example Description
1 Constant A=b+1 Statement (one line
of code)
log(n) Logarithmic While(n>1){n=n/2} Divide in half
(binary search)
n Linear For(c=0; c<n; c++) Loop
{1+=1}
n*log(n) Linearithmic Mergesort, E ective sorting
Quicksort algorithms
n^2 Quadratic For(){For(){}} Double loop
n^3 Cubic For(){For(){For(){}}} Triple loop
2^n Exponential Trying to break a Exhaustive search
password by
generating all
possible
combinations
Asymptotic notation (Big Ω)
Best-case asymptotic running time (“lower bound”)
ff
, It provides a lower limit on how quickly the running time can grow as the input size
increases.
If Big-O <= then Big Ω >=
T(n) = Ω(f(n)) if and only if there exists
positive constants c and n0 such that
T(n) >= c * f(n)
for all n >= n0
Asymptotic notation (Big θ)
“Precise bound”
It indicates that the running time grows at the same rate as a speci c function for
su ciently large input sizes.
If Big-O <= and Big Ω >=
then Big θ =
T(n) = θ(f(n)) if and only if there exists
positive constants c1, c2 and n0 such that
c1 * f(n) <= T(n) <= c2 * f(n)
for all n >= n0
Primary school algorithm
Karatsuba multiplication
Big-O: 3 recursive steps of n/2-digit numbers — O(n^(log2(3))) = O(n^1.59)
Input: two n-digit positive integers x and y.
Output: the product x * y
Assumption: n is a power of 2
—————
If n = 1 then
compute x * y in one step and return the result
Else
a, b := rst and second halves of x
c, d := rst and second halves of y
ffi fi fi
, compute p := a + b and q := c + d using grade school addition
recursively compute ac := a * c, bd = b * d, and pq := p * q
compute adbc := pq - ac - bd using grade school addition
compute 10^n * ax + 10^(n/2) * adbc + bd using grade school addition
return result
Recursive multiplication algorithm
Big-O: 4 recursive steps — O(log(max(a, b))
Input: two n-digit positive integers x and y.
Output: the product x * y
Assumption: n is a power of 2
—————
If n = 1 then
compute x * y in one step and return the result
Else
a, b := rst and second halves of x
c, d := rst and second halves of y
recursively compute ac := a * c, ad := a * d, bc := b * c, and bd = b * d
compute 10^n * ac + 10^(n/2) * (ad + bc) + bd using grade school addition
return result
NOTE: in karatsuba we only need to compute ac, bd and (a + b)(c + d)
Calculation complexity - recursive algorithms
Master method
T(n) <= a * T(n/b) + O(n^d)
Where
a: number of recursive calls
b: input size shrinkage factor (how fast my input shrinking with code, recursive call)
d: exponent in running time of the “combine step”
1. Sorting
The naive approach for sorting an array of integers: get the minimum, print it, remove it from the
array, and repeat.
fi
, Selection sort
Big-O: n the number of items in the list — O(n^2)
This is comparison-based sorting algorithm. It works by dividing the input list into two parts: a
sorted and unsorted portion. The algorithm repeatedly selects the smalles (or largest, depending
on the order) element from the unsorted portion and moves it to the end of the sorted portion.
This is repeated until the entire list is sorted.
Steps:
1. Start with the rst element of the list as the current minimum (of maximum)
2. Compare the current minimum with each element in the unsorted portion of the list. If a
smaller element is found, update the current minimum to that element.
3. Once iterated through the unsorted portion and the smallest element is identi ed, swap it with
the rst element in the unsorted portion. This e ectively moves it to the end of the sorted
portion.
4. Repeat the process, considering the next element (i = i +1) as the current minimum, and
comparing it with the remaining unsorted elements.
5. Continue these steps until the entire list is sorted. The sorted portion will grow, and the
unsorted portion will shrink with each iteration.
3 17 5 25 1 Sorted = ∅
Current min Unsorted = A
Compare cur_min with all other elements.
1 < 3; therefore set cur_min = A[1] and swap 3 with 1
1 17 5 25 3 Sorted = A[0]
Unsorted = A[1] -
Current min
A[4]
3 < 17; swap 17 with 3
1 3 5 25 17 Sorted = A[0] - A[1]
Unsorted = A[2] -
Current min
A[4]
1 3 5 25 17 Sorted = A[0] - A[2]
Unsorted = A[3] -
Current min
A[4]
17 < 25; swap 25 with 17
1 3 5 17 25 Sorted = A[0] - A[4]
Unsorted = ∅
Input: unsorted array A of length n
fi
fi ff fi
0. Introduction
Asymptotic notation (Big-O)
Worst-case asymptotic running time (“upper bound”)
It provides the upper limit on how the running time of an algorithm grows as the input size
increases
Suppress:
- Constant factors – too system-dependent
- Lower-order items – irrelevant for large inputs
T(n) = O(f(n)) if and only if there exists
positive constants c and n0 such that
T(n) <= c * f(n)
for all n > n0
Classes of algorithmic complexity
Growth rate Name Code example Description
1 Constant A=b+1 Statement (one line
of code)
log(n) Logarithmic While(n>1){n=n/2} Divide in half
(binary search)
n Linear For(c=0; c<n; c++) Loop
{1+=1}
n*log(n) Linearithmic Mergesort, E ective sorting
Quicksort algorithms
n^2 Quadratic For(){For(){}} Double loop
n^3 Cubic For(){For(){For(){}}} Triple loop
2^n Exponential Trying to break a Exhaustive search
password by
generating all
possible
combinations
Asymptotic notation (Big Ω)
Best-case asymptotic running time (“lower bound”)
ff
, It provides a lower limit on how quickly the running time can grow as the input size
increases.
If Big-O <= then Big Ω >=
T(n) = Ω(f(n)) if and only if there exists
positive constants c and n0 such that
T(n) >= c * f(n)
for all n >= n0
Asymptotic notation (Big θ)
“Precise bound”
It indicates that the running time grows at the same rate as a speci c function for
su ciently large input sizes.
If Big-O <= and Big Ω >=
then Big θ =
T(n) = θ(f(n)) if and only if there exists
positive constants c1, c2 and n0 such that
c1 * f(n) <= T(n) <= c2 * f(n)
for all n >= n0
Primary school algorithm
Karatsuba multiplication
Big-O: 3 recursive steps of n/2-digit numbers — O(n^(log2(3))) = O(n^1.59)
Input: two n-digit positive integers x and y.
Output: the product x * y
Assumption: n is a power of 2
—————
If n = 1 then
compute x * y in one step and return the result
Else
a, b := rst and second halves of x
c, d := rst and second halves of y
ffi fi fi
, compute p := a + b and q := c + d using grade school addition
recursively compute ac := a * c, bd = b * d, and pq := p * q
compute adbc := pq - ac - bd using grade school addition
compute 10^n * ax + 10^(n/2) * adbc + bd using grade school addition
return result
Recursive multiplication algorithm
Big-O: 4 recursive steps — O(log(max(a, b))
Input: two n-digit positive integers x and y.
Output: the product x * y
Assumption: n is a power of 2
—————
If n = 1 then
compute x * y in one step and return the result
Else
a, b := rst and second halves of x
c, d := rst and second halves of y
recursively compute ac := a * c, ad := a * d, bc := b * c, and bd = b * d
compute 10^n * ac + 10^(n/2) * (ad + bc) + bd using grade school addition
return result
NOTE: in karatsuba we only need to compute ac, bd and (a + b)(c + d)
Calculation complexity - recursive algorithms
Master method
T(n) <= a * T(n/b) + O(n^d)
Where
a: number of recursive calls
b: input size shrinkage factor (how fast my input shrinking with code, recursive call)
d: exponent in running time of the “combine step”
1. Sorting
The naive approach for sorting an array of integers: get the minimum, print it, remove it from the
array, and repeat.
fi
, Selection sort
Big-O: n the number of items in the list — O(n^2)
This is comparison-based sorting algorithm. It works by dividing the input list into two parts: a
sorted and unsorted portion. The algorithm repeatedly selects the smalles (or largest, depending
on the order) element from the unsorted portion and moves it to the end of the sorted portion.
This is repeated until the entire list is sorted.
Steps:
1. Start with the rst element of the list as the current minimum (of maximum)
2. Compare the current minimum with each element in the unsorted portion of the list. If a
smaller element is found, update the current minimum to that element.
3. Once iterated through the unsorted portion and the smallest element is identi ed, swap it with
the rst element in the unsorted portion. This e ectively moves it to the end of the sorted
portion.
4. Repeat the process, considering the next element (i = i +1) as the current minimum, and
comparing it with the remaining unsorted elements.
5. Continue these steps until the entire list is sorted. The sorted portion will grow, and the
unsorted portion will shrink with each iteration.
3 17 5 25 1 Sorted = ∅
Current min Unsorted = A
Compare cur_min with all other elements.
1 < 3; therefore set cur_min = A[1] and swap 3 with 1
1 17 5 25 3 Sorted = A[0]
Unsorted = A[1] -
Current min
A[4]
3 < 17; swap 17 with 3
1 3 5 25 17 Sorted = A[0] - A[1]
Unsorted = A[2] -
Current min
A[4]
1 3 5 25 17 Sorted = A[0] - A[2]
Unsorted = A[3] -
Current min
A[4]
17 < 25; swap 25 with 17
1 3 5 17 25 Sorted = A[0] - A[4]
Unsorted = ∅
Input: unsorted array A of length n
fi
fi ff fi
