Homework Help is Here – Start Your Trial Now!
Engineering
Data Structures and Algorithms
I have been confused for a while on worst case, best case, and average case for algorithms. I get that big O noation is worst case, Omega notation is best case, and theta is average notation, but I don't get how are we supposed to be able to tell what the function (ex. (n), (log n), ( n log n), etc.) is for those algorithms and why are they those functions? I got an AI generated response earlier, which was helpful in pointing out what kinds of algorithms might have (n) or (log n), but what I really want to know is how can I tell if a function is going to specifically be (log n) vs (n log n), (n), etc., why is it that function and which functions (log n) (n), (n log n), are better or faster than others.

I have been confused for a while on worst case, best case, and average case for algorithms. I get that big O noation is worst case, Omega notation is best case, and theta is average notation, but I don't get how are we supposed to be able to tell what the function (ex. (n), (log n), ( n log n), etc.) is for those algorithms and why are they those functions? I got an AI generated response earlier, which was helpful in pointing out what kinds of algorithms might have (n) or (log n), but what I really want to know is how can I tell if a function is going to specifically be (log n) vs (n log n), (n), etc., why is it that function and which functions (log n) (n), (n log n), are better or faster than others.

icon
Related questions
Question

I have been confused for a while on worst case, best case, and average case for algorithms. I get that big O noation is worst case, Omega notation is best case, and theta is average notation, but I don't get how are we supposed to be able to tell what the function (ex. (n), (log n), ( n log n), etc.) is for those algorithms and why are they those functions?

I got an AI generated response earlier, which was helpful in pointing out what kinds of algorithms might have (n) or (log n), but what I really want to know is how can I tell if a function is going to specifically be (log n) vs (n log n), (n), etc., why is it that function and which functions (log n) (n), (n log n), are better or faster than others. 

Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 4 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Follow-up Questions
Read through expert solutions to related follow-up questions below.
Follow-up Question

Thanks for the help. This explaines a good bit. I understand the part about omega(n), since that part of the code is linear and going one by one through the array/info, but why is the other part log n. I guess I am just confused about how each extraction and restoration operation equate to being log n. I haven't worked too much with log problems espically in graphs.

Solution
Bartleby Expert
SEE SOLUTION
Follow-up Question

Thanks for the answer. While this is helpful in understanding worst, best, and average case a bit better, what I am really wanting to know is how do I look at an algorithm like quick sort and determine whether the time complexity is log n, n, n^2, etc., like for this homework question: 

Show that the worst-case running time of HEAPSORT is Ω(n lg n). I am wondering why it is (n lg n) in the first place. 

Solution
Bartleby Expert
SEE SOLUTION