Look at their graphs.
Note that coefficients do not make T(n) grow near as fast as various functions of n.

Consider some functions and their common names
Now get some values of these functions for various n. (Notice chosen values of n - since log₂ are integers for powers of 2)
Finally, graph them as n gets large.

Now go back and consider how some I gave to you compare. Make a chart of values to see the rate of growth to determine which is < the other as n gets big. (To cheat, see page 111 in text.)
What we are doing is seeing when functions are asymptotically bigger(or smaller) than one another. I.E. which one grows faster than the other.

Formal Definitions

Def. f(n) = O(g(n)) iff there exists positive constants c and n_o such that f(n) < cg(n) for all n , n > n_o (g is upper bound)

Note that this is saying that f(n) is asymptotically smaller than or equal to g(n)

e.g. Suppose T(n) = (n + 1) ²
then
   T(n) is O(n²)

Verify:

let n_o = 1 and c = 4
for n > 1,        (n +1)² < 4n²

(why not n³ ) (lub)

T(n) is O(n² ) for some program means there are positive constants c and n_o such that for n > n_o we have T(n) < cn²

verify T(n) = 3n³ + 2n² is O(n³) (what does that mean?)

T(n) = 3n³ + 2n² < cn³ let c= 5, n_o = 1, then for all n > 1
3n³ + 2n² < 5n³
2n² < 2n³
n² < n³
1 < n

is T(n) also O(n⁴) ?

* Prove Theorem 3.1 (page 119) ... makes polynomials easy

(can always get a big enough c, n_o )

Theorem: If f(n)=a_mn^m + ... + a₁n + a₀ , then f(n) = O(n^m).

Proof:
hints for proof:

1. n^m * n^i-m = n^m+i-m = nⁱ
   then
2. notice if n^i-m have negative exponents => fractions
   n * fraction < n* 1.
3. Finally let c = the summation of | a_i | and n_o = 1
   e.g.,
   6n³ + 5n² +4n + 2 < 6n³ + 5n³ + 4n³ +2n³ = 17n³

OK, here is the proof:

So, f(n) = O(n^m) (assuming that m is fixed)

DONE

WHY?
Remember:
f(n) = O(g(n)) iff there exists positive constants c and n_o such that f(n) < cg(n) for all n , n > n_o
Our g(n) is n^m, let be   c

So, given:

6n³ + 5n² +4n + 2 O(?) and what might c be?
4n + 2 O(?) and what might c be?

f(n) = 1000n² + 100n - 6 < 1001n² for n > 100

• run at constant time O(1) ->
  run in time independent of inputs
• linear time ->
  time proportional to length of input
  if double length => double time
• exponential
  See here for calculations of recursive algorithms (Data Structures and Algorithms, Aho, Hopcroft, and Ullman, Addison-Wesley, 1983, ISBN 0-201-00023-7, Chapter 9)

Example 3.15 page 120 (and here)

verify
(what does that mean?)

Theta

iff there exists positive constants c₁, c₂ and n_o such that c₁g(n) < f(n) < c₂g(n) for all n , n > n_o

verify
(what does that mean?)

Example 3.18 page 121 (and here)

if upper = lower --> algorithm is "best possible"

only way to make faster is faster hardware

HOWEVER, algorithmic improvement is more useful than hardware improvement Big chart of times
another chart of times and
and suppose computer improvements

Problems: Page 115: numbers 2, 3, 5 (but use the formal definition rather than the "working definition", Page 124: Numbers 9 and 11 (Don't forget that some answers are on the book website)

If you still want more info, see MIT slides (for this class only to slide 18)