The Gateway to Computer Science Excellence
0 votes
What is difference between tightest upper bound and tightest lower bound? Give ur explanation with examples?
in Algorithms by (411 points) | 40 views
Better if you prefer standard book..for deeeper insight.

1 Answer

0 votes
The tightest upper bound and lower bound is defined for finding the time/space complexity.

For example, the complexity for bubble sort algorithm is $O(n^2)$ which can also be written as $O(n^3)$ or $O(n^4)$ as well but we chose to write the tightest bound as $O(n^2)$. Why?

Because it is closest to the actual efficiency of the algorithm. We try to generalize or get to as close as possible.

Similarly, for tightest lower bound as well.

For example, sorting N numbers takes at least NlogN time.  These results are difficult to get but they do give us the intuition that we can stop working on the algorithm at the lower bound. It is not possible to improve algorithm efficiency after this.
by Boss (18.9k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,291 answers
104,891 users