40 views
What is difference between tightest upper bound and tightest lower bound? Give ur explanation with examples?
| 40 views
0
Better if you prefer standard book..for deeeper insight.

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)

1
2
3