What is a loose bound in asymptotic notation?

Question

When describing a loose bound, can I pick any value for the proper notation that is not close at all to the actual value for the asymptotic notation? If my function is n^2 + n, could I say a loose upper bound is O(n^3), and could I say that a loose lower bound is Ω(1)? Would such statements be valid? When do I know that my loose bound is valid or not?

score 0 · Answer 1 · answered Sep 02 '20 at 06:25

From the here Difference between Big-O and Little-O Notation talking about Big-O vs little-o, it would be fine to say your n^2+n is O(n^3) and this is a loose upper bound. However most people would describe it as O(n^2) as this is more accurate and tells you that the algorithm is actually faster than O(n^3)

I think "loose bound" might come up more when something isn't completely known. For instance the naive recursive Fibonacci function:

def fibo(n):
  if n == 1 or n == 2:
    return 1
  return fibo(n-1) + fibo(n-2)

You could say that this is O(2^n) because the function makes 2 recursive calls so it's doubling at each step. However, one side of this "tree" (if you were to expand out the function calls it looks sort of like a tree) will bottom out to a base case faster than the other because it's n-1 vs n-2. This means the "tree" is lopsided and so it will actually be faster than O(2^n). Hence O(2^n) is a "loose upper bound."

Finding a tighter bound is left as an exercise to the reader ;)

What is a loose bound in asymptotic notation?

1 Answers1