0
$\begingroup$

Given two statement:

A:if inputs of a problem is online, then there is faster or equal algorithm in view of time complexity for that problem when input is offline.

B:if inputs of a problem is offline, then there is faster or equal algorithm in view of time complexity for that problem when input is online.

Which of the following statement is true?

I think A is true because each algorithm works for online inputs then it work for a offline inputs. Now we can say A is true. B is false because, consider online sorting algorithm and offline sorting algorithm, online algorithm have much more time complexity in ratio of offline versions.

$\endgroup$
3
  • $\begingroup$ Please credit the original source for all copied material. See cs.stackexchange.com/help/referencing $\endgroup$ – D.W. Mar 9 at 20:04
  • $\begingroup$ Can you provide further clarification? Is it assumed that the online algorithm can only receive one input at a time? In an actual use case the sorting algorithm should be separate from the means of accessing the input. Therefore, the time complexity of sorting would be the same, regardless of input location. I do not really understand the question. If you could provide some context, that would help a lot. $\endgroup$ – phyzyk Mar 9 at 23:17
  • $\begingroup$ Please read these Wiki pages: en.wikipedia.org/wiki/Online_algorithm and en.wikipedia.org/wiki/Competitive_analysis_(online_algorithm) $\endgroup$ – HEKTO Mar 10 at 0:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy