Big Oh Notation

An important question is: How efficient is an algorithm or piece of code? Efficiency covers lots of resources, including:

* CPU (time) usage

* memory usage

* disk usage

* network usage

All are important but we will mostly talk about CPU time in 367. Other classes will discuss other resources (e.g., disk usage may be an important topic in a database class).

Be careful to differentiate between:

1. Performance: how much time/memory/disk/... is actually used when a program is run. This depends on the machine, compiler, etc. as well as the code.

2. Complexity: how do the resource requirements of a program or algorithm scale, i.e., what happens as the size of the problem being solved gets larger.

Complexity affects performance but not the other way around.

The time required by a method is proportional to the number of "basic operations" that it performs. Here are some examples of basic operations:

* one arithmetic operation (e.g., +, *).

* one assignment

* one test (e.g., x == 0)

* one read

* one write (of a primitive type)

Some methods perform the same number of operations every time they are called. For example, the size method of the Sequence class always performs just one operation: return numItems; the number of operations is independent of the size of the sequence. We say that methods like this (that always perform a fixed number of basic operations) require constant time.

Other methods may perform different numbers of operations, depending on the value of a parameter or a field. For example, for many of the Sequence methods, the number of operations depends on the size of the sequence. We call the important factor (the parameters and/or fields whose values affect the number of operations performed) the problem size or the input size.

When we consider the complexity of a method, we don't really care about the exact number of operations that are performed; instead, we care about how the number of operations relates to the problem size. If the problem size doubles, does the number of operations stay the same? double? increase in some other way? For constant-time methods like the size method, doubling the problem size does not affect the number of operations