University of California, Santa Cruz

Prof. Paulo Franca - Spring 2000

Introduction

Syllabus

Guidelines for labs

Lab sections

Take quiz & check grades

Teta notation:

Teta(g(n)) ... is the set of functions f(n) that:

there exist positive constants c1, c2 and n0 such that:

0<= c1*g(n) <= f(n) <= c2*g(n)   for all n>=n0

Therefore a  function f(n) belongs to the set Teta(g(n)) if there exists positive constants c1,c2 such that f(n) can be "sandwiched" between c1g(n) and c2g(n) for sufficiently large values of n.

Notes:

Example:

Consider the function that expresses the worst-case running time of an insertion sort:

T(n)=  ¹/₂  n² - 3 n

In order to show that f(n) = n² , we must determine c1, c2 and n0 so that:

c1 n²  <=    ¹/₂   n² - 3 n  <= c2  n²

^Important:

^{the function g(n) must be represented in a simple form. g(n) must be simpler to evaluate than f(n). Some students "discover" that f(n) could be its own g(n) with c1,c2=1 ! Remember that g(n) is a set, and we want to represent the set by the simplest form possible.}

because c1 and c2 must be positive ... c2>=1/2    n>=7   c1<=1/14

details?