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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.