Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Decision Trees, #11
#1
In proving a tight lower bound for a class of algorithms, one tries to establish, over all possible algorithms:
  1. the worst possible best case

  2. the worst possible worst case 

  3. the best possible best case

  4. the best possible worst case
This question comes from the decision trees section. If you are proving a lower bound for a class of algorithms, then you have to be looking for the best possible case. But I'm not sure if you are looking for the worst possible best case or best possible best case. My analysis goes like this: 

Lets say you take the class of comparison sort algorithms. The best case for bubble, insertion, selection, quick & merge sort are n, n, n^2, nlogn and nlogn, respectively. If you take the worst possible best case, then you have a lower bound as n^2. But, insertion, bubble, merge, and quick sort perform better in their best cases; therefore, this doesn't actually bound the entire class of algorithms from the bottom. On the other hand, if you take the best possible best case, you have a lower bound of n, which is not asymptotically tight compared to algorithms like selection, merge, and quick sort.

Anyone have the correct answer or any thoughts?
Reply
#2
I haven't had my coffee yet, so I won't confuse the both of us trying to explain the question, but I do have the answer.

As of last semester's CS201 course, the answer to this exact question, with these exact choices was:
  The best possible worst case.

It was given to us straight from the unicorn's mouth during a round of question and answer from the decision tree questions before a test in that course. I still have a copy of my print-out for the day and this particular question is marked as having received a direct and definitive answer from Dr. Lusth. 

I will come back to this question as soon as I feel up to working through the logic in a concise enough manner to not embarrass myself and confuse you further, but hopefully someone else will step up before I put my helmet on.
Everything looks sarcastic on the internet. 
Reply
#3
Ok, so, I have beseeched the dark, silky, mocha goddess and imbibed the jittery nectar. Let us now don our helmets and descend to the depths of this man's logic.

This line represents units of time taken for the function f(x) to reach a solution:

0      Ω--->          arguably average runtime          <---O    ∞
<-----|---------------------------------------------------------------|------>
faster('better cases')                             slower('worse cases')


Ω omega represents the lower bound
O omicron represents the upper bound


When we speak of lower bounds, I believe we are speaking of an estimate of the "at least" amount of time we might expect the algorithm to take to reach a solution in its average execution. That is, in the line above, the position of the omega represents the lowest amount of time in which the given function is likely to complete a solution(barring some strange exception). If the function is Ω of something, we are saying, "This function will take at LEAST (greater than or equal to) the same amount of time that this other something takes, to complete a solution." So, if f(x) = Ω g(x), we are saying that f(x) will take at LEAST the same amount of time to complete as g(x) does, but it might take even longer.

So, if I am correct about all of this above:

In order to find the tight lower bound of the function f(x) from the line above, we want to know the imaginary location of that pipe symbol (|) by the omega in the line.

Let's look at the answer choices:

---best of the best case---

We do not care about the instances which lie to the left of that pipe symbol, as they represent the best of the best cases. Some of those run-times might be nearly instantaneous due to lucky input, and we really can't make use of that sort of data.

---worst of the worst case---

We also do not care about the points on the line beyond the Omicron pipe to the right, as those points represent the worst of the worst cases which might take roughly average time, or could extent to infinity, and beyond >.0

---the worst possible best case---

This is where it gets tricky. If we look at the worst possible best case, it might sound like we are on the right track. Honestly someone else might better explain conceptually why this isn't the correct choice. I am tempted to argue that worst best and best worst, at least in so far as the English language are concerned, both represent to the listener the concept of average-ness. This strikes me as a very "shower thought" and perhaps I will debate it the next time I wash my hair. That being said, in my mind, it comes down to which one conveys the idea of starting where things are worst, and working until you find the fastest or best of those worst things... and the next option conveys that concept better in my opinion.

---the best possible worst case---

In my mind, this option represents the best definition of the Omega pipe location. When you describe the best possible worst case, you are looking at all the slowest solutions you can imagine, viewing the problem from a sort of pessimistic perspective and, working back to the best of the worst cases, you state that: "you can never expect that things will run faster than this". I do have to wonder where one draws that line for 'best of worst' and 'worst of best'. It is probably a math thing, right? >.0


Some of the information here can certainly be argued as "point of view" rather than solid logic, and I might come back to alter this post even if no one bothers to shoot my 'logic' full of holes. There are probably a couple of 'mathies' in this course who would love nothing more than to show you some inequality expressions from the text book and insist that those series of symbols speak greater truth than English ever could. Let us hope they visit your question.

Forgive me if I've made things worse, and have a good one!

MIT and Khan academy are good people. Check out their lessons on the subject and see what sort of impression you get of the matter.

https://www.khanacademy.org/computing/co...a-notation
Everything looks sarcastic on the internet. 
Reply
#4
Some very good analyses above. You are thinking like computer scientists!

Here is a simple process of elimination tack. Bounds for algorithm are always for the worst case, unless otherwise specified. So that leaves WPWC (worst possible worst case) or BPWC. We all know we can write algorithms that are not optimal. In fact, we can always make an slow algorithm slower, if we want. So the WPWC over a class of algorithms can be arbitrarily bad. That leaves:

BPWC

Viola! Balalaika! Bordonua!
Reply
#5
(08-19-2017, 10:20 PM)lusth Wrote: Some very good analyses above. You are thinking like computer scientists!

Here is a simple process of elimination tack. Bounds for algorithm are always for the worst case, unless otherwise specified. So that leaves WPWC (worst possible worst case) or BPWC. We all know we can write algorithms that are not optimal. In fact, we can always make an slow algorithm slower, if we want. So the WPWC over a class of algorithms can be arbitrarily bad. That leaves:

BPWC

Viola! Balalaika! Bordonua!

When you say that bounds for algorithms are always for the worst case, are you referring to the worst case input? I think I'm a little confused. If so, how can you determine a lower bound for an algorithm (or class of algorithms) if you aren't considering input that allows it have an optimal running time?
Reply
#6
"in the worst case" means input that causes the worst case behavior.

Any algorithm can have log n best case behavior by caching the results of certain inputs in, say, a red-black tree. So best case behavior doesn't usually help you much in determining how bad an algorithm can be.

A single algorithm can have really bad worst-case behavior (as noted previously), so any particular worst-case behavior doesn't help in figuring out what is a "reasonable" worst case behavior. But if you can survey all possible algorithms to solve a particular problem, then you just pick the best of the worst-case behaviors to establish a lower bound on that class of algorithms.
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)