DSC 40B Lecture 3

Growth Rates

Common Growth Rates

: Constant : Logarithmic : Linear : Linearithmic : Quadratic : Cubic : Exponential

Asymptotic Notation

vs. and

ignores constant factors and lower-order terms

Big Theta

We say that if there are positive constants such that for all :

Basically means we can sandwich between two versions of

Upper bounding tips

• Promote lower-order positive terms
• Drop negative terms

Lower bounding tips

• Drop lower-order positive terms
• Promote and cancel negative lower-order terms if possible
• Cancel negative lower-order terms with big constants by breaking off a piece of high term

Caution

• To upper bound a fraction , you must
  • Upper bound the numerator,
  • Lower bound the denominator,
• To lower bound a fraction , you must
  • Lower bound the numerator,
  • Upper bound the denominator,

Big-O and Big-

Sometimes we only care about an upper bound.
if “grows at most as fast as

Examples:

Big O

We say that if there are positive constants such that for all :

Sometimes we only care about a lower bound. if “grows at least as fast as fast” as .

Big Omega

We say that if there are positive constants such that for all :

Theta, Big O, and Big Omega

• If , then and
• If and then

In other words (symbols)

Analogies

• is kind of like
• O is kind of like
• is kind of like

Other notations

• if grows “much slower” than
• if grows “much faster” than

Properties of

1. Symmetry: If , then
2. Transitivity: If and then
3. Reflexivity:

• If and then
• If and then

Proving/Disproving Properties

• Start by trying to disprove
• Finding a counterexample
• If you can’t disprove, maybe it’s true

1. State the assumptions (constants)
2. Use the assumptions (chain of inequalities)

Sums of Theta

If and then Used when analyzing sequential code

Products of Theta

If and then Used when analyzing loops Careful: If the inner loop index depends on the outer loop, you have to be more careful.

Asymptotic Notation Practicalities

Asymptotic notation is not just used to denote algorithms, e.g. “n choose k” and error of sample mean in Central Limit Theorem

Faux Pas

• Don’t include constants or lower-order terms in the notation
• Don’t include base in logarithm
• Don’t misinterpret the meaning of
• Time complexity is not a complete measure of efficiency
  • Asymptotic notation “hides the constants”

Main Idea

Time complexity is not the only way to measure efficiency, and it can be misleading. Sometimes even a algorithm is better than a algorithm, if the data size is small.