Worst Case & Asymptotic Analysis

Guiding Principles of Worst Case and Asymptotic Analysis  

1. Worst Case is useful for the following reasons:

  • Gives a bounded running time for large inputs n
  • Hard to define a “normal” input
  • Easier to analyze

7n \log n is objectively better than 1/2n^2

2. Asymptotic Analysis

  • Don’t care about coefficients
  • Discard lower order terms
  • Don’t lose any predictive power
  • Constants are machine-dependent

Goal: Find algorithms as close to order n as possible

f(n) \in O(g(n)) \exists c > 0 and n_0>0 s.t.

(\forall n>n_0)(0\le f(n)\le cg(n))

This entry was posted on Thursday, July 5th, 2007 at 7:30 pm and is filed under Design and Analysis of Algorithms. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to “Worst Case & Asymptotic Analysis”

  1. John Williams Says:
    July 11, 2007 at 7:17 pm

    You can put text in the middle of a LaTex equation that is not italicized using the \text{insert this regular text here} command. There are also specific commands to insert space in an equation, because spaces are ignored in the equation environment.

    \Leftrightarrow \exists \, n_0 > 0 \text{ and }c >0\text{ s.t. }

    You could write

    f(n) \in O(g(n)) \text{ if and only if }(\exists c>0)(\exists n_0 > 0)(\forall n>n_0)(0 \leq f(n) \leq c \cdot g(n))

    for example.

Leave a Reply