Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Question 35
Quote:35. T or F: If f = O(g), then there exists a problem size above which f is runs faster than or the same time as g, even in the best of cases.

Confused by wording. Can anyone restate the question in better terms?
UA ACM Vice President
ACM has bi-weekly meetings Tuesdays at 5:15pm
We're UA's best organization for CS majors (website)
Join us on Slack for all kinds of discussion channels (including one for CS403)
lol! This is one ugly sentence for sure. Let's put on our helmets and walk through this together. 

T or F: If  f = O ( g )  " then there exists a problem size above which f is always runs faster than or the same time as g, even in the best of cases."

Line 1: I always confuse myself with big O, so stop me at the line I seem to have gone off track: 

L2: If I am not mistaken, O means "faster than or equal to, assuming sufficiently large n"

L3: So for my own sake I will substitute the conditional for the words: "If f  = faster than or equal to g, given large enough n" and attempt to show the sentence doesn't conflict. 

L4: "then there exists a problem size above which" ( here we cover the requirement of sufficiently large n from Line 3, so True at this point )

L5: "f is always runs faster than or the same as g"   (grammar bomb fallout is obvious, but we can assume it should read 'f always runs faster than or the same as g', which we were looking for at Line 3, so we can say True at this point.)

L6: "even in the best of cases" : I imagine this is a point of confusion, as I found it a bit off-putting myself. Best of cases for f? Best of cases for g? Does it matter which or both? I'll break this part down by thought as well, though I am afraid this is where my logic will read a little iffy:

      L7: Best of cases for f only : in the best of cases for f, we are assuming f is running fast, optimally, better than any other cases, so this definitely matches Line 3 assuming f was truly faster or equal to g in the average case already. 

      L8: Best of cases for g : one example of best case for g might be running f and g both with 1 billion negative numbers. f always runs regardless of positive or negative numbers, and thus takes a while to finish up. g on the other hand includes validation logic at line one to abort the function with default return value(s) if a negative number is detected. Here we see an instance where we have typical f case, best g case, and sufficiently large n, and yet the function g runs faster than f. This SEEMS to make the statement in Line 3 FALSE

      L9: Best of cases for f and g both :  Taking the logic from Line 8, we can imagine a scenario where either f or g might suddenly perform radically better in its best case scenario, regardless of the size of n. When the wording "best case" is used as a conditional, and we assume it applies to both f and g, or even just g, it is very hard to see an evaluation of True.

MY CONCLUSION: The statement, including "even in the best of cases" causes this equation to evaluate FALSE.

Everything looks sarcastic on the internet. 
Good analysis. And yes, despite what your definition of "is" is, it is a spurious addition.

Forum Jump:

Users browsing this thread: 1 Guest(s)