The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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   

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   

   Growth of Functions - Computer Science, Old Dominion University   

If you have any more questions, please write back.

 - Doctor Douglas, The Math Forum   
Associated Topics:
High School Calculators, Computers
High School Functions

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.