1
$\begingroup$

In Trivial lower bounds we just need to count the number of items in the input that needs to be processed and the number of items that need to be generated and the trivial lower bound time is then the sum of these two found numbers. My question is , we know that the time complexity = number of times the basic operation is repeated as a function of the input size * the time it is taken to preform the basic operation once. So as we can see from the formula of the time complexity that it depends on the basic operations not on the number of inputs and output items. So how does the trivial solution is used to compute the lower bound ( worst time complexity of best algorithm) then ?

$\endgroup$
1
$\begingroup$

The trivial bound assumes that the program has to read the entire input. This is usually, but not always, the case. Similarly, it assumes that the program has to write each output item separately. This is usually, but not always, the case.

Since the program has to read the entire input, it has to do some operation for each input item. Similarly, it has to so some operation for each output item. This gives you the trivial bound, in terms of the number of basic operations.

Since we are usually only interested in complexity up to constant factors (big O complexity), the actual time that a basic operation takes doesn't enter the picture at all.

$\endgroup$
  • $\begingroup$ So mean that this method assumes for each one input there is a one correspondence basic operation that will be done to it ? i.e the number of inputs = number of basic operations ? $\endgroup$ – John adams Apr 15 '20 at 18:06
  • $\begingroup$ At least one basic operation per input. $\endgroup$ – Yuval Filmus Apr 15 '20 at 18:06
  • $\begingroup$ Many thanks for ur reply . But this method doesn't take into account the number of operations for each input , so surly it will give a wrong answer about the lower bound ? $\endgroup$ – John adams Apr 15 '20 at 18:11
  • 1
    $\begingroup$ Not at all. Nobody said the lower bound should be tight. If the output depends on the entire input (at least in the worst case), then any algorithm has to "touch" the entire input. Therefore its running time must be at least proportional to the input size. Sometimes this is a very bad bound, sometimes it's asymptotically tight (that is, tight up to a constant factor). $\endgroup$ – Yuval Filmus Apr 15 '20 at 18:13
  • $\begingroup$ Its clear now , but can you give an example when this method will give a very bad bound ? $\endgroup$ – John adams Apr 15 '20 at 23:39

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.