CS61B(13): Asymptotics I

Posted on | In , |

This is the lecture note of CS61B - Lecture 13.

Efficiency comes in two flavors:

  • Programming cost (course to date. Will also revisit later).
    • How long does it take to develop your programs?
    • How easy is it to read, modify, and maintain your code?
      • More important than you might think!
      • Majority of cost is in maintenance, not development!
  • Execution cost (from today until end of course).
    • How much time does your program take to execute?
    • How much memory does your program require?

From now, we start focusing on execution cost, learning kinds of data structures and algorithms. Hope you will enjoy it.

Runtime Characterization

Approach 1

One technique can be used is to measure execution time in seconds using a client program.

1
2
3
4
5
public static void main(String[] args) {
    int N = Integer.parseInt(args[0]);
    int[] A = makeArray(N);
    dup1(A);
}

We can use tools like:

  • Physical stopwatch.
  • Unix has a built in time command that measures execution time.
  • Princeton Standard library has a Stopwatch class.

Measuring runtime in seconds is easy to measure, meaning is obvious. However, it requires large amounts of computation time, and result varies with machine, compiler, input data, etc.

Approach 2A

Approach 2B

Compare Algos

In most cases, we care only about asymptotic behavior, i.e. what happens for very large N.

  • Simulation of billions of interacting particles.
  • Social network with billions of users.
  • Logging of billions of transactions.
  • Encoding of billions of bytes of video data.

Algorithms which scale well (e.g. look like lines) have better asymptotic runtime behavior than algorithms that scale relatively poorly (e.g. look like parabolas).

Simplification

Since we don't need to do rigorous, mathmatically runtime charaterization, maybe we can simplify the above tech to make it much clearer and simpler.

Simplification 1

Simplification 2

Simplification 3

Simplification 4

So, take a summary,

Big-Theta

Let's see the formal definition of Big-Theta:

Big-O

We used Big Theta to describe the order of growth of a function. We also used Big Theta to describe the rate of growth of the runtime of a piece of code.

Big-O is used for upper bounds.