Chapter 2 overview

What are the goals for chapter 2?
The goals for chapter 2 are:

  • Start using frameworks for describing and analyzing algorithms.
  • Examine two algorithms for sorting - Insertion sort and merge sort.
  • See how to describe algorithms in pseudocode.
  • Begin using asymptotic notation to express running-time analysis.
  • Learn the technique of "divide and conquer" in the context of merge sort.

...

How do we analyze an algorithm's running time?

What two things does the time taken by an algorithm depend on?
Two things the time taken by an algorithm depends on are:

  1. The input's size.
  2. To what degree the input is already sorted.

Can the running time of an algorithm differ between two inputs of the same size?
Yes, the running time of an algorithm can differ between two inputs of the same size.

Input size

Can what is considered the input size differ depending on the problem?
Yes, what is considered the input size differs depending on the problem.

What is the input size usually?
The input size is usually the number of items.

What could be the input size if you're multiplying two integers?
If you're multiplying two integers, the input size could be the total number of bits in the two integers.

What's a type of algorithm where the input size is usually described using multiple numbers?
A type of algorithm where the input size is usually described using multiple numbers is graph algorithms.

What two numbers are typically used to express the running time of a graph algorithm?
The two numbers that are typically used to express the running time of a graph algorithm are:

  1. The number of vertices of the input graph.
  2. The number of edges of the input graph.

Running time

What is the running time of an algorithm?
The running time of an algorithm is the number of primitive operations (steps) executed.

How should you define steps?
You should define steps to be machine independent.

What is the time complexity for a line of pseudocode?
The time complexity for a line of pseudocode is or constant time.

What is true even if two lines of pseudocode take different amounts of time to execute?
Even if two lines of pseudocode take different amounts of time to execute, the execution still takes a constant amount of time.

What is the symbol for the amount of time the code at line number of a block of pseudocode takes?
The symbol for the amount of time the code at line number takes of a block of pseudocode is .

What is assumed about the line of pseudocode for the time complexity of it to be constant?
For the time complexity of a line of pseudocode to be constant, it is assumed that the line only has primitive operations.

What happens to the running time of a line of pseudocode if the line has a subroutine call?
If a line of pseudocode has a subroutine call, the call takes constant time while the subroutine might not.

What happens to the running time of a line of pseudocode if the line uses operations other than primitive ones?
If a line of pseudocode uses operations other than primitive ones, the running time might be more than constant time.

Analysis of insertion sort

...

How many times does the condition of a for and while loop execute in comparison to the body of the loop?
In comparison to the body of a for and while loop, the condition executes one more time than the body of the loop.

What is the generic structure for an equation that describes the running time of an algorithm?
The generic structure for an equation that describes the running time of an algorithm is:

What is the equation for the running time of the insertion sort algorithm where is the input size?
The equation for the running time of the insertion sort algorithm, where is the input size, is:

What do the values of depend on?
The values of depend on the input.

What is the best case scenario for insertion sort?
The best case scenario for insertion sort is when the input is already sorted.

What is the value of in the best case scenario?
The value of in the best case scenario is 1.

What is the equation for the running time of insertion sort in the best case scenario?
The equation for the running time of insertion sort in the best case scenario is:

What type of function can the function of the best case scenario running time be expressed as?
The function of the best case scenario running time can be expresses as a linear function.

What is the worst case scenario for insertion sort?
The worst case scenario for insertion sort is when the input is in reverse order.

What is the value of in the worst case scenario?
The value of when the input is in reverse order is .

What is also known as?
is also known as an arithmetic series.

What is an arithmetic series equivalent to?
An arithmetic series is equivalent to .

What is equivalent to?
is equivalent to .

What is the equation for the running time of insertion sort in the worst case scenario?
The equation for the running time of insertion sort in the worst case scenario is:
What type of function can the function of the worst case scenario running time be expressed as?
The function of the worst case scenario running time can be expresses as a quadratic function.

Worst-case and average-case analysis

What do we usually concentrate on when finding the running time of an algorithm?
When finding the running time of an algorithm, we usually concentrate on the worst-case running time.

What are the two reasons we concentrate on finding the worst-case running time?
The two reasons we concentrate on finding the worst-case running time are:

  1. The worst-case running time is a guaranteed upper bound for any input.
  2. For some algorithms, the worst case happens often.

Why don't we analyze the average case running time?
We don't analyze the average case running time because the average case is often as bad as the worst case.

Order of growth

What two things do we do to the formula for running time in order to ease analysis?
The two things we do to the formula for running time in order to ease analysis are:

  1. Drop lower-order terms.
  2. Ignore the coefficient in the leading term.

Can you say that the running time equals , , etc?
No, you can't say that the running time equals , , etc.

How do you express the order of growth for the running time?
To express the order of growth for the running time, you write .

When is one algorithm considered to be more efficient than another algorithm?
One algorithm is considered to be more efficient than another algorithm when its worst-case running time has a smaller order of growth.

Designing algorithms

What type of algorithm is insertion sort?
Insertion sort is an incremental algorithm.

From Gemini

Incremental algorithms are a class of algorithms that solve a problem by gradually building up a solution from smaller sub-solutions.

Divide and conquer

What are the three steps of a divide and conquer algorithm?
The three steps of a divide and conquer algorithm are:

  1. Divide - Break the problem down into a number of subproblems which are smaller instances of the same problem.
  2. Conquer - Solve the subproblems recursively.
  3. Combine - Join the subproblem solutions together to give a solution to the original problem.
From Gemini

The base case is the smallest and simplest instance of the problem that can be solved directly without further division. It's the termination condition for the recursive process.

Merge sort

How is the array initially set up with merge sort?
The array is initially set up with merge sort like , where and .

How are each of the subproblems defined using this array setup?
Each of the subproblems are defined using this array setup by changing and as each subproblem is recursed.

What happens during the divide step of merge sort?
During the divide step of merge sort, the input array is split into two subarrays, and , where is the halfway point of .

What happens during the conquer step of merge sort?
During the conquer step of merge sort, the two subarrays are recursively sorted.

What happens during the combine step of merge sort?
During the combine step of merge sort, the two sorted subarrays are combined into a single array again using a procedure called .

When does the recursion for merge sort stop?
The recursion for merge sort stops when the subarray has 1 element.

What is the pseudocode for merge sort?
The pseudocode for merge sort is:

Merge-Sort(A,p,r)
	if p < r       // Check for base case
		q = floor((p + r) / 2) // Divide
		Merge-Sort(A,p,q)      // Conquer
		Merge-Sort(A,q+1,r)    // Conquer
		Merge(A,p,q,r)         // Combine

What does an input array with 8 elements look like as merge sort sorts it?
An input array with 8 elements looks like this as merge sort sorts it:
Merge Sort on 8 Element Array.png

What does an input array with 11 elements look like as merge sort sorts it?
An input array with 11 elements looks like this as merge sort sorts it:
Merge Sort on 11 Element Array.png

Merging

What are the inputs of the procedure?
The inputs of the procedure are:

  • - The array.
  • - Indices such that .

What is the output of the procedure?
The output of the procedure is a single sorted subarray in .

What can represent in divide and conquer algorithms?
In divide and conquer algorithms, can represent the input size of a given subproblem.

...

Analyzing divide-and-conquer algorithms

What is used to describe the running time of a divide-and-conquer algorithm?
To describe the running time of a divide-and-conquer algorithm, a recurrence (equation) is used.

...