CTK Exchange Front Page Movie shortcuts Personal info Awards Reciprocal links Privacy Policy Cut The Knot! MSET99 Talk Games & Puzzles Arithmetic/Algebra Geometry Probability Eye Opener Analog Gadgets Inventor's Paradox Did you know?... Proofs Math as Language Things Impossible My Logo Math Poll Other Math sit's Guest book News sit's
|Store|

CTK Exchange

 Subject: "Omega Functions??" Previous Topic | Next Topic
 Conferences The CTK Exchange College math Topic #64 Printer-friendly copy     Email this topic to a friend Reading Topic #64
Dynamo
Charter Member
2 posts
Feb-24-01, 09:50 AM (EST)

"Omega Functions??"

 I am an undergraduate, and I have been asked by a collegue what the omega function is. I have never come accros it, could someone point me to somewhere where I could find out about it, two questions that have been asked are:Given two sets S1 and S2, and a real # x, find whether there exists an element from S1 and an element from S2 whose sum is exactly x. The algorithm should run in time O(nlogn) where n is the total # of elements in both setsand:Construct an example for which interpolation search will use Omega(n) comparisons for searching in a table of size n.I have an idea of how to answer this but not with the Omega() function.Thanks for any help.

alexb
Charter Member
672 posts
Feb-24-01, 10:11 AM (EST)

1. "RE: Omega Functions??"
In response to message #0

 >I am an undergraduate, and I >have been asked by a >collegue what the omega function >is. I have never come >accros it, could someone point >me to somewhere where I >could find out about it, By the sound of it, Omega() and O() are the same. It's not a function but rather a notation that sets a bound on growth rate:|O(x)| < const·x