Week 2: Algorithm Analysis

To make the images bigger, click on them.

What does each part of summation notation mean?

What is a “Basic Operation” in an algorithm?

A basic operation is the operation that gets repeated the most as the input grows.

It also tends to be the most significant operation that seems to be driving the algorithm forward.

What does the ← symbol represent in pseudocode?

It represents the equals symbol: =

What does n represent in pseudocode?

The number of inputs, or the number of elements in an array.

Name the 8 most common growth families, in order from smallest growth to largest growth.

SMALLEST GROWTH

O (1) = constant

O (log n) = logarithmic

O (n) = linear

O (n log n) = linearithmic

O (n²) = quadratic

O (n³) = cubic

O (2ⁿ) = exponential

O (n!) = factorial

LARGEST GROWTH

What does this algorithm do? Trace through it to find out.

(Assume n = 3 and A = [7, 2, 10] )

It is trying to find the largest element in the array.

In this algorithm, which important operation gets repeated the most as the input grows?
(Which is the basic operation?)

The Comparison: A[ i ] > m

We know this is the basic operation because the algorithm is fundamentally about finding the largest element.
So naturally, the comparison operation in this code will be the most valuable/important to driving the algorithm forward.

What does this algorithm do? Trace through it to find out.

(Assume n = 4)

It calculates the sum of squares.

1² + 2² + 3² …..

In this algorithm, which important operation gets repeated the most as the input grows?
(Which is the basic operation?)

s = s + i * i

How many times does the basic operation run? Write it as a summation.

Whenever you see a summation that repeatedly adds up 1, what formula should you use to simplify it?

You should use the formula:

end-start + 1

Example question: How do you simplify the following?

end-start + 1

= n-1+1

= n

Answer: n

Example Question: How do you simplify the following?

end-start + 1

= (n-1)-0+1

= n

Answer: n

Whenever you see a summation that repeatedly adds up i, what formula should you use to simplify it?

You use the formula:

Note: This stops working once your starting value of i is anything other than 0 or 1.

Example Question: How do you simplify the following summation?

Use K(K + 1) / 2, just substitute K for whatever value is at the top of the summation.

So:

K(K+1) / 2

= (n-1)(n-1 + 1) / 2

= (n-1)(n) / 2

= n(n-1) / 2

Answer: n(n-1) / 2

Simplify the final summation from the earlier question.

Then, explain why we simplify summations when working with algorithms.

Since the summation adds up 1 each time, we can simplify it by applying our formula:

end-start + 1

= n - 1 + 1

= n

The reason we simplify summations is because:

#1 We want a direct formula where we can substitute n.
When you plug in the value of n, it will immediately tell you how many times the basic operation ran. This is much more convenient than having to add up 1+1+1+1…..n times.

For example, in this problem, since our simplification is n, and we know the value of n is 4, we know that our basic operation ran n = 4 times.

#2 We want to figure out what the growth rate is in Big O notation.
For example, here, we simplified it to n. This means that our growth rate is O(n) = linear growth.

What does the following algorithm do?

Trace through it assuming n = 3, and assuming you have the following 2D matrix:

[  5   2   7  ]
[  1   9   3  ]
[  4   8   6  ]

It sums up all the elements in a 2D array.

In this algorithm, which important operation gets repeated the most as the input grows?
(Which is the basic operation?)

s = s + A[ i ][ j ]

How many times does the basic operation run? Write it as a summation.

Then, simplify the summation and identify the Big O classification.

What does Best Case refer to when working with algorithms?

Best Case = Represents a case where an algorithm runs the minimum number of times and requires the least amount of work. This is usually because you got lucky and the input data happened to be in some perfect arrangement.

Ex. A search algorithm only having to run once because the value being searched for is the first element in the array.

What does Average Case refer to when working with algorithms?

Average Case = Represents the average number of steps taken to complete an algorithm.

What does Worst Case refer to when working with algorithms?

Worst Case = Represents a case where an algorithm runs the maximum number of times and requires the most work.

Ex. A search algorithm having to go through every single element in the array because the item being searched for is at the end of the array.

What does this algorithm do? Trace through it to find out.

(Assume n = 4 and A = [3, 8, 6, 2] and k = 8)

It searches for an element, k.

In this algorithm, which important operation gets repeated the most as the input grows?
(Which is the basic operation?)

The basic operation is: A[ i ] ≠ K

How many times does the basic operation run? Write it as a summation.

Then, simplify the summation and identify the Big O classification.

In this same algorithm, is there a best and a worst case scenario?

And if so, which of these cases does our summation represent?

Yes, there is a Best and a Worst case.

The Worst Case: If we have the array [3, 8, 6, 2] with n = 4 and we make 4 comparisons, this means we had to search through every element of the array in order to find our desired value.

As a result, we made the maximum number of comparisons (n comparisons), which takes the most work.

The Best Case: The best case is that we only have to look at the first element in the array in order to find our desired value. This means we only make one comparison.

Which case does Tom want you to focus on in class?

Usually only worst case, which is represented by summation (unless he specifies otherwise).

What does this algorithm do? Trace through it to find out.

(Assume n = 4 and A = [7, 3, 5, 2] )

It is the insertion sort; it sorts the elements of an array in ascending order.

In this algorithm, which important operation gets repeated the most as the input grows?
(Which is the basic operation?)

The basic operation is: A[ j ] > v

We know this because the algorithm’s goal is to sort elements in ascending order; so naturally, the most important/repeated operation is the one that actually compares elements in the array.

How many times does the basic operation run? Write it as a summation.

Then, simplify the summation and identify the Big O classification.

What does this algorithm do? Trace through it to find out.

(Assume n = 16)

It halves the value of n by powers of 2 repeatedly.

In this algorithm, which important operation gets repeated the most as the input grows?
(Which is the basic operation?)

i = i / 2

However, you could pick the basic operation to be i >= 1 or even the sum: sum = sum + 1. It actually doesn’t matter which one you pick, because you get the same big O. However, you should still strive to pick the “key operation” which tends to be the one that drives the algorithm forward the most.

What does this algorithm look similar to?

It looks similar to a logarithm.

How many times does the basic operation run? Write it as a summation.

Then, simplify the summation and identify the Big O classification.

When we classify things using Big O, how come we are allowed to just throw parts of the equation away?

Because for an expression like 3n + 7, the 7 becomes more and more irrelevant as the growth progresses.

The same thing goes for expressions like: 3n² + 6n + 7; The other terms become increasingly more irrelevant, and the 3n² ends up dictating most of the growth/progression.

What does Big O Notation actually describe?

Big O notation describes the “upper bound” of a function’s growth rate.

What does Big Omega (Big Ω) actually describe?

Big Omega (Big Ω) describes the “lower bound” of a function’s growth rate.

What does Big Theta (Big θ) actually describe?

Big Theta (Big θ) describes the exact bound for an algorithm’s growth rate. It tends to be sandwiched somewhere in the middle between the lower and upper bound.

Which notation does Tom expect us to know/use?

Only Big O notation.

What is Big O notation testing for?

Big O is testing to see if your proposed growth function grows at least as fast as the actual function for very large inputs.

For example, let’s say that:

The actual function is: f(n) = 2n + 6

The proposed growth function is: g(n) = n

Big O tries to create an upper boundary with the proposed growth function (g(n)) to see if it grows at a similar rate to the original function. In order to do so, it multiplies g(n) by some constant, c:

If we say the constant is, c = 4

then: c x g(n)

= 4 x n

= 4n

When we compare these two functions on a table for all values of n, we see the following pattern:

n	2n+6 (the actual function)	4n (the proposed growth function)
1	8	4
2	10	8
3	12	12
4	14	16
5	16	20
6	18	24
7	20	28
8	22	32
9	24	36
10	26	40

As soon as n =3, the proposed growth function becomes equal to and constantly stays above the actual function. This is an example of Big O.

What is Big Omega and Big Theta notation testing for?

Big Omega notation is checking to see if you can multiply your proposed growth function by a value so that it stays below the actual function.

Big Theta notation is checking to see if the actual function can be trapped between two different versions of the growth function; Each version is multiplied by a different constant, one constant will keep the growth function below, and the other above the actual function forever.

Match the graph to the notation:

Big Theta (Big θ)

A trick for remembering which one this is is by looking at the symbol: θ. The symbol makes it look like its sandwiched in between two other layers (the upper bound and lower bound).

Big Omega (Big Ω)

Big O

What is the shortcut to remembering Big O, Big Omega, and Big Theta?

• Big-O = execution will take at MOST that long

• Big-Ω (Omega) = execution will take at LEAST that long

• Big-Θ (Theta) = execution will take THAT long

What does this algorithm do? Trace through it to find out.

(Assume n = 4 and A = [7, 8, 2, 3] )

It finds the greatest element in an array.

In this algorithm, which important operation gets repeated the most as the input grows?
(Which is the basic operation?)

A[ i ] > maxval

How many times does the basic operation run? Write it as a summation.

Then, simplify the summation and identify the Big O classification.

What does this algorithm do? Trace through it to find out.

(Assume n = 4 )

It halves the value of n on every iteration of the while loop.

Which is the basic operation?

i = i / 2

How many times does the basic operation run? Write it as a summation.

Then, simplify the summation and identify the Big O classification.

This cannot be written as a summation because nothing is being summed up. The value of i is being divided, so we must use logarithms.