search
Log In
0 votes
69 views
What is difference between tightest upper bound and tightest lower bound? Give ur explanation with examples?
in Algorithms 69 views
0
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.

Related questions

0 votes
2 answers
1
246 views
What is the running time of the following function (specified as a function of the input value)? void Function(int n){ int i=1; int s=1; while(s<=n){ i++; s=s+i; } } $O(n)$ $O(n^2)$ $O(1)$ $O(\sqrt n)$
asked Mar 30 in Algorithms Lakshman Patel RJIT 246 views
4 votes
4 answers
2
465 views
Among the following asymptotic expressions, which of these functions grows the slowest (as a function of $n$) asymptotically? $2^{\log n}$ $n^{10}$ $(\sqrt{\log n})^{\log ^{2} n}$ $(\log n)^{\sqrt{\log n}}$ $2^{2^{\sqrt{\log\log n}}}$
asked Feb 11 in Algorithms Lakshman Patel RJIT 465 views
0 votes
1 answer
3
247 views
How to check if a given recurrence relation is in a format that is valid to apply Master’s Theorem? Also, how to distinguish between Master’s Theorem and extended Master’s Theorem?
asked Jun 12, 2019 in Algorithms lolster 247 views
1 vote
2 answers
4
449 views
If $T1(n) = \Theta(f(n))$ & $T2(n) = \Theta(f(n))$ Then, Is $T1(n) + T2(n) = O(f(n))$ If yes, then how?
asked May 26, 2019 in Algorithms shubhojit1412 449 views
...