Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Comparing algorithms using Order Notation
I want to clarify that the following phrases denote that the input size can be anything. i.e. not a sufficiently large input size. 
  "in all cases"
  "in some cases"
  "regardless of input size"

If the above is true I want to confirm that a question like "If f = _(g), then algorithm f can run in the same time as g, in some cases" would always be true because it could always run in the same time with a small input size. 

And if the above is true I would also expect "in all cases" or "regardless of input size" to always be false if the input size is small.

If I am wrong can you give counter examples and explain why?
when the input size is zero or empty, your argument may be valid. But in that case, there is no need or benefit for comparison.
Yeah, the question though is what constitutes "unless otherwise specified" regarding whether we need to account for sufficiently large n. "In all cases", "in some cases" and "regardless of input size" could all be interpreted as "otherwise specifying" that we don't need to assume sufficiently large n. I think we need a clarification from Dr Lusth.
I would consider "in some cases" to invalidate the assumption of "input size sufficiently large" and "worst-case behavior". I will clarify, however, what exactly I mean by "in some cases" on the test.

Forum Jump:

Users browsing this thread: 1 Guest(s)