Review of Algorithm Analysis

Topical Information

The purpose of this quiz is to give you a chance to focus your knowledge of analyzing algorithms.

Quiz Information

Questions

What is meant when we say that a function (let's call it f) is in O(g)?


    It means that the function f has a rate of growth (kinda-like a slope,
    but not exactly), at worst comparable to g.  And by 'comparable', we
    mean ignoring constant factors and addends as well as lower-order terms.

Show the general formula used in analyzing the complexity of an algorithm. (Hint: Something about summing products of probabilities and..?)


    The general approach is to add up the products of all inputs'
    probabilities and their 'counts' (counting whatever relevant statistic
    of their code execution or memory usage we were focusing on):

              ---------
              \
               \
                >     p * c
               /       i   i
              /
              ---------
                ALL i

    This will give us the appropriate analysis expression/function to work
    with to determine its 'Big-O' group (if not 'Big-Theta'...).

Briefly explain the difference(s) between Big-O, Big-Omega, and Big-Theta.


    Big-Omega consists of all functions which grow at least as fast as the
    reference function.

    Big-O consists of all functions which grow at most as fast as the
    reference function.

    Big-Theta is the intersection of Big-O and Big-Omega.

Given the following algorithm fragment:

    RANGE k FROM s TO e BY 1
        a[k] = b[k-s] + c[k-s]*d[k-s]
        INVOKE restore PASSING a,  s,  e
                       RECEIVING a
    END RANGE

And knowing that the PD|restore| algorithm is O(n), estimate the order of the given fragment.


    O(n^2)

Why is this so?


    The restore algorithm is linear and is called from within
    the given fragment which is a linear pass through the same segment of
    the [presumed] array that restore is given to work on.

    Since we have a linear algorithm taking place once per pass of a linear
    walk through the data, we have a multiplicative combination.

Given two algorithms to accomplish the same task, one with time analysis n^3-3 and the other with time analysis 16n+8, which would you prefer generally?
```
    The linear one:  16n+8.
```
[Specifically] When would you prefer the 'losing' algorithm? (Remember that we are dealing with problem sizes for n here...)
```
    When n^3-3 < 16n+8, we'd prefer the losing algorithm.  Plugging this
    into my graphing calculator, I find that when n < 4, I'd prefer the
    cubic algorithm.
```
Name at least one algorithm which is of each of the following orders. (Try to name an algorithm which has not already been referred to in the question set --- at least not in Big-O terms.)
1. O(n^3)
```
    matrix multiplication
```
2. O(log_2(n))
```
    binary search
```
3. O(n)
```
    linear search
```
4. O(1)
```
    add two numbers
```