
Store







CTK Exchange
Dynamo
Charter Member
2 posts 
Feb2401, 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 sets and: 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. 

Alert  IP 
Printerfriendly page  Edit 
Reply 
Reply With Quote  Top 


alexb
Charter Member
672 posts 
Feb2401, 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 

Alert  IP 
Printerfriendly page  Edit 
Reply 
Reply With Quote  Top 


You may be curious to visit the old CTK Exchange archive.
Front page
Contents
Copyright © 19962018 Alexander Bogomolny
[an error occurred while processing this directive]

Advertise
