Explain the terms Tight bound, Upper
bound
Ans
Big O is the upper bound, while Omega
is the lower bound. Theta requires both Big O and Omega, so that's why it's
referred to as a tight bound (it must be both the upper and lower bound).
For example, an
algorithm taking Omega(n log n) takes at least n log n time but has no upper limit.
An algorithm taking Theta(n log n) is far preferential since it takes AT LEAST
n log n (Omega n log n) and NO MORE THAN n log n (Big O n log n).
Upper bound
Ans
One use of the terms lower bound and
upper bound is in array processing. If you dynamically allocate an array's size
during program execution then these terms are used to loop through the
array.
in linear programming upperbound is
some sort of contraint on the variable. Such as in sales problem , number of
items sold must not be greater than something in one state,something in other
states...etc. but I guess in sorting and searching there are some contraints
like number of iterations must not exceed o(n)... etc
No comments:
Post a Comment