#Is 'best case O(1) running time` the same as Ω(1)?

1 messages · Page 1 of 1 (latest)

brittle nightBOT
#

<@&987246717831381062> please have a look, thanks.

brittle nightBOT
#

While you are waiting for getting help, here are some tips to improve your experience:

Code is much easier to read if posted with syntax highlighting and proper formatting.

If nobody is calling back, that usually means that your question was not well asked and hence nobody feels confident enough answering. Try to use your time to elaborate, provide details, context, more code, examples and maybe some screenshots. With enough info, someone knows the answer for sure.

Don't forget to close your thread using the command </help-thread close:1027500463647621170> when your question has been answered, thanks.

turbid linden
#

what is Ω(1), I never saw this notation

austere pawn
#

It's the lower bound for running time

tulip magnet
#

no it's not

#

it means "my algo is not better than this"

#

or "my algo is worse than this"

#

and best/worst/average case have nothing to do with that. case analysis is about restricting the input domain and then, after that, doing the analysis

#

the analysis itself is always determined and bound by the worst case that the input domain allows

#

for all of them

#

since it says "for all x..."

#

so any bad x will drive the analysis

austere pawn
#

Is this correct: bubble sort will run O(n) best if the input is already sorted and O(n^2) when the input is not sorted?

#

Okay I think I get it. Bubble sort running time is Ω(1) since at best it will always take O(n) which is worse than constant time?

tulip magnet
#

u have to stop with that best abd worse thing. that's incorrect

#

any of those. complexity things is always bound by the worst input type

#

omega means ur worse than sth else

#

its usually used when u want to prove that sth cannot be done better

#

i. e. finding a lower bound

#

for example, comparison based sorting is in Omega(n log n)

#

meaning that it's impossible to find any algorithm that would be faster than this

austere pawn
tulip magnet
#

im not sure what u want to express. but again, complexity stuff is always. bound by the worst input

#

there is no "this is best case O(...) and worst case O(...)"

#

O(...) by definition says "for all input"

#

so a single bad input dominates the whole analysis

#

if u want to do case analysis, u have to restrict the input domain first

#

and then do an analysis on that restricted function

#

but im just repeating myself now

#

i have the feeling that u don't understand what I'm saying. if that's the case, please just tell what's unclear instead

austere pawn
#

I encountered blog posts that say an algorithm, runs worst case of O(someValue) and sometimes at best (anotherValue). Ix this not correct?

tulip magnet
#

what they do is a case analysis. where u restrict the input domain and then, after that, do a complexity analysis

#

on the function restricted to certain types of input only

#

and then, within this restriction, its still the worst input that dominates everything

#

so a best case analysis is the algo restricted to the type of input that works best for the algo, but then, within that category, the worst input makes the complexity

iron heron
#

For a given input size, n, I think the following are colloquial:
Big-O notation describes the behavior of a function when it takes the largest number of operations possible,
Big-Θ (theta) notation describes the behavior of a function "on average,"
Big-Ω (omega) describes the behavior of a function when it takes the fewest number of operations possible.

So in the specific case you asked about, I believe O(1) implies Ω(1) as well, since if it takes a constant number of operations in the worst case, then it takes a constant number of operations always (including in the best case). Though generally, the two symbols represent different things.

brittle nightBOT
#

Closed the thread due to inactivity.

If your question was not resolved yet, feel free to just post a message to reopen it, or create a new thread. But try to improve the quality of your question to make it easier to help you 👍

austere pawn