363 views

1 Answer

0 votes
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.

Related questions

0 votes
0 votes
1 answer
1
Crackca asked Nov 20, 2021
301 views
We are having 4 sorted sub-lists of size n/4, What is the time complexity to merge them in a single sorted list?