Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Word "or" in true-false questions
#1
Quote:If f = ω ( g ) , then algorithm f always runs faster than or takes the same time as g.

Assuming sufficiently large n and worst-case behavior, f would always run faster than, never take the same time as, g. If I follow the logical principle of the inclusive OR, this statement would indeed be true, even though f will never take the same amount of time as g. Am I reading this question correctly?
Reply
#2
(09-04-2017, 06:24 PM)elmines Wrote:
Quote:If f = ω ( g ) , then algorithm f always runs faster than or takes the same time as g.

Assuming sufficiently large n and worst-case behavior, f would always run faster than, never take the same time as, g. If I follow the logical principle of the inclusive OR, this statement would indeed be true, even though f will never take the same amount of time as g. Am I reading this question correctly?

ω, >, Little Omega, Always slower than

So f takes more time than g, and is slower always. So False.

The correct answer for f always being faster than or equal to g would be:

f = O(g)

If the possibility of same time exists, it will be an upper case symbol or theta. This is my understanding at least.
Reply
#3
ianbway is correct. f = ω ( g ) means that the f grows faster than g, which implies that f will take more time to run than g. for example n^3 = ω (n^2). This means n^3 grows faster than n^2, and n^3 will take more time than n^2.
Reply
#4
(09-04-2017, 06:59 PM)ianbway Wrote:
(09-04-2017, 06:24 PM)elmines Wrote:
Quote:If f = ω ( g ) , then algorithm f always runs faster than or takes the same time as g.

Assuming sufficiently large n and worst-case behavior, f would always run faster than, never take the same time as, g. If I follow the logical principle of the inclusive OR, this statement would indeed be true, even though f will never take the same amount of time as g. Am I reading this question correctly?

ω, >, Little Omega, Always slower than

So f takes more time than g, and is slower always. So False.

The correct answer for f always being faster than or equal to g would be:

f = O(g)

If the possibility of same time exists, it will be an upper case symbol or theta. This is my understanding at least.

Oh, duh. Thank you ianbway; that was sheer carelessnes on my part.
Reply
#5
Actually, the question is kind of ambiguous. Logical or means only one has to be true, so, literally speaking, your original take would be correct. If f = ω ( g ), then f is slower than or equal to g, in the same way that if 5 < 6, then 5 <= 6. My intent, though, was for the answer to be false, so for the test, I'll word things better.
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)