Analyzing Algorithms

Question 1

What is the purpose of algorithm analysis?

Answer 1

To compare the effectiveness of algorithms without having to consider implementation details, the speed of the computer system used, and test data. As n grows, how does the number of operations grow?

Question 2

How do you analyze the speed of an algorithm?

Answer 2

• count the number of steps or operations needed
• look at it as a function of the size of the problem
• you can look at either the average number of steps, or the
  maximum number of steps

Question 3

What is the speed of a linear search?

Answer 3

O(n)

Question 4

What is the speed of a binary search?

Answer 4

O(log(n))

Question 5

What happens when you double n with the different typical bounds?

Answer 5

O(log n): adds c to time
O(n): double the time
O(nlogn): not much slower than O(n)
O(n^2): time4
O(n^3): time8
O(2^n): time^2
O(n!): don’t even try

Question 6

What is the speed of an ordered insert?

Answer 6

O(n): only one loop, goes through one element at a time, essentially a linear search

Question 7

What is the speed of our simple sorting algorithms?

Answer 7

O(n^2): contains two nested loops

Question 8

What is an example of a better sorting algorithm?

Answer 8

Merge sort:
- split the array into two small arrays
- sort the two halves (using two merge sorts)
- merge the two sorted halves into a sorted array after the
2 merge sorts have returned

Question 9

What is the speed of a merge sort?

Answer 9

O(nlogn)