|
|Store|
|
|
|
|
|
|
|
CTK Exchange
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 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 |
Printer-friendly page | Edit |
Reply |
Reply With Quote | Top |
|
|
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 |
|
|
Alert | IP |
Printer-friendly page | Edit |
Reply |
Reply With Quote | Top |
|
|
You may be curious to visit the old CTK Exchange archive.
|Front page|
|Contents|
Copyright © 1996-2018 Alexander Bogomolny
[an error occurred while processing this directive]
|
Advertise
|
Printer-friendly copy
Email this topic to a friend