Summary
Summary of Data Structures and Algorithms
- Course
- Institution
Summary containing information on the slides, notes, and book.
[Show more]
Seller
Follow
mchelleh
Content preview
Data Structures and Algorithms0. 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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller mchelleh. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $16.60. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
71498 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now