1

The task

I am trying to find out the asymptotic tight bound for a function, f(n) = 1/n^5. It will be great if someone can provide suggestions or solutions on how to find the asymptotic tight bound for f.

What I have come up with

We can safely assume that 0 < f(n) <= 1. Therefore we can say the upper bound complexity of f is O(1).

Also we can say the lower bound complexity of f is Omega(1/n^5). So, the asymptotic tight bound of this function is Theta(1/n^5).

Hermann Döppes
  • 1,373
  • 1
  • 18
  • 26
kenneth
  • 13
  • 4

1 Answers1

1

A critique of your solution

While you arrived at a conclusion, the arguments you gave are not particularly good.

The upper bound

While we certainly have f in O(1), this is entirely irrelevant. You do not use it and I do not see any way in which it could be useful.

The lower bound

The lower bound is correct but you do not give any reason why. One might argue for this to be trivial but the triviality should be pointed out explicitly if this is the line of reasoning you want to follow.

The tightness

Without any further reasoning you claim your lower bound to be tight.

A (trivial) solution

For any function f, the function f is a tight bound for itself.

The Homework

Prove this rigorously yourself.

Hermann Döppes
  • 1,373
  • 1
  • 18
  • 26