Theta Notation: Complexity and the Step Function

Date: 02/05/2001 at 09:49:08
From: Aaron Boxer
Subject: Use of a Greek symbol in a formula

I found the follow equation in a paper:

     m >= theta(n(log r)/(log log r))

The paper uses the Greek symbol theta which I can't reproduce here.
Also, >= means greater than or equal to in this context.

I've been searching Web dictionaries and can't find a definition for 
theta that makes sense in the context of this paper. The paper is,

   IEEE Transactions on Computers, VOl 48, No. 11, Nov. 1999, pg. 
        1214-1227. "The Necessary Conditions for Clos-Type
        Nonblocking Multicast Networks."

Thanks for any help you can give me.
Aaron Boxer

Date: 02/05/2001 at 10:50:29
From: Doctor Douglas
Subject: Re: Use of a Greek symbol in a formula

Hi Aaron, and thanks for writing.  

Let me use the "at" symbol, @, to denote the Greek letter theta.

If the function @(z) is used without specifying it (especially by
engineers and physicists), then it often means the Heaviside step
function, which is simply

     @(z) = 0 for z < 0
     @(z) = 1 for z >= 0

This function is just a step function where the argument hits zero, 
and the notation @(z) is simply used when one would like a simple, 
single-line expression so that things don't get too messy.

I'm not entirely sure that this is indeed what is used in the IEEE 
reference, but it seems likely to me.

I hope this helps. Please write back if you need more help with this.

- Doctor Douglas, The Math Forum
  http://mathforum.org/dr.math/   

Date: 02/05/2001 at 11:34:15
From: Aaron Boxer
Subject: Re: Use of a Greek symbol in a formula

Dr. Math,

In this context I'm pretty sure it's not the step function because 
the value expected is a count of some entity which I'm sure can be an
integer greater than 1. Could this be a shorthand for "round up to
the nearest positive integer?"

Thanks for the quick response.
Aaron Boxer

Date: 02/05/2001 at 12:16:16
From: Doctor Douglas
Subject: Re: Use of a Greek symbol in a formula

Hi again, Aaron.

Thanks for writing back. I think the following is what you're after.

You may be familiar with "Big Oh" notation, which establishes an upper
bound on the scaling behavior (or complexity behavior, in the 
algorithmic context). E.g., the number of operations N(n) is O(n^2 
log n).  

For lower bounds, the symbol that is used is capital Omega, e.g. N(n) 
is Omega(n log n). And if you can bound the scaling/complexity both 
above and below by simply choosing different constants, the 
complexity behavior is established fairly tightly. The symbol used 
here is capital Theta.

Here's where I found this explanation (see section 1.4.3):
   
   Data Structures: 1: Introductory Material - M. S. Schmalz
   http://www.cise.ufl.edu/~mssz/DatStrucAlg/DSAintro.html   

   Growth of Functions - Computer Science, Old Dominion University
   http://www.cs.odu.edu/~toida/nerzic/content/function/growth.html   

If you have any more questions, please write back.

 - Doctor Douglas, The Math Forum
   http://mathforum.org/dr.math/