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."

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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search