Algorithm complexity

Notes

Goodrich Chapter 3 Notes

date structure - systematic way of organizing and accessing data

algorithm - step by step procedure for performing a task in a fixed amount of time

To time algorithms: distinguish between:

• wall time (less fair, dependent on environment) time.time
• number of cpu cycles used by algorithm (better) time.clock
• timeit/built in profiling tool (best)

Moving beyond experimental analysis:

• Independence from hardware/software
• Use higher level analysis
• Account for all possible inputs

Worse case versus average case

• Algorithm speed changes with different inputs
• Worst case is easiest to determine
• Average case requires probability distribution over inputs

$ \overline{t} = \int_{\Omega} t(\mathbf{x}) p(\mathbf{x}) d\mathbf{x} $

Seven functions for algorithm analysis:

1. Constant function

2. Logarithmic function

3. Linear function

4. n log n function

5. Quadratic function

6. Cubic/polynomial function

7. Exponential function

Example: find_max function

• Runtime: 2 statements always run, plus the for loop
• Probabilit/worse case/average case;
• The worst case assumes we have to run biggest = k every time through the for loop
• Average case analysis:
• If there are n numbers total, and if we have just looked at j numbers so far, the probability that the jth number will be the new largest of j numbers is 1/j
• The number of times biggest number is updated, when we run n times, is the sum of each probability,

$ H_{n} = \sum_{j=1}^{n} \dfrac{1}{j} $

nth Harmonic number

Harmonic numbers increase as $ O(\log n) $ - sometimes this is the source of a "magic log" term that appears.

Geometric sums:

• For any integer n>= 0 and any real number a > 0, a neq 1,

$ \sum_{i=1}^{n} a^i = 1 + a + a^2 + \dots + a^{n-1} + a^n = \dfrac{ a^{n+1} - 1}{a-1} $

This applies to finding the largest integer representable with n bits:

$ 1 + 2 + 4 + 8 + \dots + 2^{n-1} = 2^n - 1 $

Big O notation:

• If we have two functions f(n) and g(n) mapping positive integers to positive real numbers, wthen we say f(n) is O(g(n)) if, for a real constnat,

$ f(n) \leq c g(n) $

for $ n \neq n_0 $

"f(n) is gib-O of g(n)

Alt: "f(n) is order of g(n)"

Alt: "f(n) is O(g(n))"

Big o notation allows ignoring constant factors and all lower order terms

Big omega notatino:

• Big O means less than or equal to
• Big Omega means greater than or equal to
• Take the same two functions f(n) and g(n),
• We say that f(n) is Omega(g(n)) if

$ f(n) \geq c g(n) $

Example: 3 n log n - 2 n is Omega(n log n)

Asymptotic analysis:

• To compare algorithms, look at two things:
  • Growth rates of algorithms as n increases
  • Maximum problem size (n) that can be solved as t increases
• Examples of algorithm analysis:
  • Length of list - O(1)
  • Accessing element of list - O(1)
  • Finding maximum: worst case vs aerage case
  • Prefix averages
  • Three-way disjointness
  • Element uniqueness

Prefix averages:

• If we want to find average of sequence S of n numbers, in another sequence A, such that A[j] is average of first j numbers,

$ A[j] = \dfrac{ \sum_{i=0}^{j} S[i] }{j+1} $

3 implementations;

• Implementation 1: nested for loops (poor performance, O(n^2))
• Implementation 2: uses colon indexing notation, like $ sum(S[0:j+1]) $, but no better performance, still O(n^2)
• Implementation 3: keep a running total, and use a cumulative algorithm

Three way set disjointness:

• Finding items that are in all 3 sets (if not, 3 sets are disjoint)
• 2 implementations:
  • Triple nested for loop, if a==b==c (wastes time, O(n^3))
  • Double nested for loop, if a==b, then another for loop, if b==c, O(n^2)

Sorting as an algorithm tool:

• Sort before searching. Sorted function is O(n log n)
• Limits cost to cost ofsearch

Justifying algorithm cost:

• Proof by example/counter-examkple
• Proof by contradiction/contrapositive
• use of DeMorgan's Law
• Induction and loop invariants

induction example:

• To prove Fibonacci number nl, F(n), is less than 2^n: First show $ F(1) < 2^1, F(2) < 2^2 $
• Then show $ F(n) < 2^{n-2} + 2^{n-1} $
• Then we know $ F(n) < 2^n $

Loop invariant:

• Prove a statement L about a loop
• Show L0 (initial claim) is true before the loop is run
• Show that if L(j-1) is true before an iteration, then L(j) is true after an iteration
• Final statement, Lk implies L is true.

Skiena Chapter 1 and 2 Notes

Analyzing algorithms

RAM model of computation - each simple operation takes exactly one time step. Loops and subroutines are not simple operations.

Algorithms can be understood and studied in a language- and machine-independent manner.

Three ways of looking at runtime:

• worst-case complexity
• average-case complexity
• best-case complexity

Why average case complexity so difficult? To illustrate: casino example.

Try to project what will happen if you bring n dollars into a casino to gamble. The best case, that you walk out owning the place, is possible but so unlikely that you should not even think about it. The worst case, that you lose all n dollars, is easy to calculate and distressingly likely to happen. The average case, that the typical bettor loses 87.32% of the money that he brings into the casino, is difficult to establish and its meaning subject to debate. What exactly does average mean? Stupid people lose more than smart people, so are you smarter or stupider than the average person, and by how much? Card counters at blackjack do better on average than customers who accept three or more free drinks. We avoid all these complexities and obtain very useful result by just considering the worst case.

That's concisely expressing in language the complexity of the parameter space $ \mathbf{x} $. The average time is expressed mathematically as:

$ \overline{t} = \int_{\Omega} t(\mathbf{x}) p(\mathbf{x}) d \mathbf{x} $

where $ t(\mathbf{x}) $ is algorithm time as a function of the input parameters (this is the function that maps the input parameter values to the output, the computational cost. The probability distribution $ p(\mathbf{x}) $ is the probability distribution that integrates to 1 when integrated over the entire input parameter domain $ \Omega $:

$ \int_{\Omega} p(\mathbf{x}) d \mathbf{x} = 1.0 $

Note: this comes from the definition of the average of a function, from calculus 2:

$ \overline{f}(x) = \dfrac{1}{b-a} \int_{a}^{b} f(p) dp $

Big O, Big Omega, Big Theta

Big O:

• $ f(n) = O(g(n)) $ means $ c g(n) $ is an upper bound on $ f(n) $. There exists a constant such that $ f(x) \leq c f(x) $ for $ n \geq n_0 $

Big Omega:

• $ f(n) = \Omega(g(n)) $ means $ c g(n) $ is a lower bound on $ f(n) $. There exists constant c such that $ f(n) \geq c g(n) $ for all $ n \geq n_0 $

Big Theta:

• $ f(n) = \Theta(g(n)) $ means the function is bounded by a function $ g(n) $ within two values of constants, $ c_1 g(n) $ forming a lower bound and $ c_2 g(n) $ forming an upper bound, for $ n \geq n_0 $

Example question: is $ 2^{n+1} = \Theta(2^n) $?

Using exponent properties, and the definition of $ \Theta(n) $,

$ 2^{n+1} = 2 \times 2^{n+1} $

and there are two constants $ c_1 = 1 $ and $ c_2 = 3 $ such that

$ 1 \times 2^n \leq f(x) \leq 3 \times 2^{n} $

Another question: is $ (x+y)^2 = O(x^2 + y^2) $?

By expanding the quantity on the left hand side, and determining the number of operations,

$ x^2 + 2xy + y^2 = O(x^2) + O(xy) + O(y^2) $

If $ x \leq y $ then the term $ 2xy \leq 2 y^2 \leq 2 (x^2 + y^2) $

If $ y \leq x $ then the middle term $ 2xy \leq 2 x^2 \leq 2 (x^+y^2) $

Heuristics

Heuristics:

Algorithms, whatever their big Oh class, take generally the same time for n=10

Any algorithm with $ n! $ runtime is impractical for $ n \geq 20 $

Algorithms with a runtime of $ 2^n $ have a greater operating range, but become impractical for $ n > 40 $

Linear time and n log n time algorithms are practical for inputs of a billion items

An O(log n) algorithm hardly breaks a sweat for any imaginable value of n

List of functions

List of functions, in increasing order of dominance (more thorough than the Goodrich book):

• Constant functions $ f(n) = 1 $
• Logarithmic functions $ f(n) = \log n $
• Linear functions $ f(n) = n $
• Superlinear functions $ f(n) = n \log n $
• Quadratic functions $ f(n) = n^2 $
• Cubic functions $ f(n) = n^3 $
• Exponential functions $ f(n) = c^n $
• Factorial functions $ f(n) = n! $

The sum of two functions is governed by the dominant one:

$ O(f(n)) + O(g(n)) \rightarrow O(\max(f(n),g(n))) $

The product of two functions is governed by the dominant one:

$ O(f(n)) \times O(g(n)) \rightarrow O(f(n) \times g(n)) $

Analyzing two sort functions

Algorithmic Analysis of Sort Functions

Questions

Goodrich Chapter 3 Questions

Sum of first n even numbers

Question R-3.6: What is the sum of the first n even numbers, 0..2n, for n > 0?

Answer: Use the sum of integers formula,

$ \sum_{k=0}^{n} 2k = 2 \sum_{k=0}^{n} k = 2 \dfrac{n(n+1)}{2} = n(n+1) = n^2 + n $

Sum of first n even numbers is $ n^2 + n $.

Solving 3 way disjointedness problem in n log n time

Question C-3.35: Assuming it is possible to sort n numbers in O(n log n) time, show it is possible to solve 3-way set disjointedness problem in O(n log n) time.

Answer: First, we sort 3 sets. That takes 3 * n log n units of time.

Then we can iterate over each element of a, which costs us n, and inside of that loop we can perform a binary search, which costs us log n, for an overall cost of n log n.

If we find b in a, then we perform another binary search for c in a. This will cost us log n.

Is the worst case then still O(n log n)? Worst case is, every element in A also in B, so we perform two binary searches each time. 2 * log n still does not cost us that much.

finding 10 largest elements

Question C-3.36: Describe an efficient algorithm for finding the 10 largest elements of a sequence of size n. What is the runtime of this algorithm?

Answer: sort n elements in O(n log n) time.

• Get 10 items from the back (biggest) - or if you want the smallest, from the front.

O(n) algorithm calling O(n2) algorithm

Question C-3.38: Show that $ \sum_{i=1}^{n} i^2 $ is O(n^3).

Answer: This is the notation we use when we need to say, "we are running a loop, and inside the loop calling a function whose cost is O(i^2)."

We know (via the story about Carl Gauss - 5050):

$ \sum_{i=1}^{n} i = \dfrac{n(n+1)}{2} \sim O(n^2) $

We can also write:

$ \sum_{i=1}^{n} i^2 = \dfrac{n(n+1)(2n+1)}{6} $

(Derivation requires some series manipulation, starting with sum over k^3 and eventually getting to k^2

This shows that when an algorithm that runs n times, O(n), calls an algorithm that runs in O(i^2) time, it results in an O(n^3) algorithm overall

Run a scaling analysis to show Python sorted function is n log n

Question P-3.57: Perform experimental analysis to test hypothesis that Python's sorted() function runs in O(n log n) time.

Answer: see https://charlesreid1.com:3000/cs/python/src/master/algorithm_complexity/test_sorted.py