I analyzed my algorithm and I deduced that in the best case it requires n^3 iterations while in the worst case it requires n^4 iterations. Then I asserted that my algorithm is in Omega(n^3) and in BigO(n^4). Is this assertion correct and useful?
(sorry for the format but I’m not able to add LaTeX text, so if you can please tell me how to format this I will edit soon, thanks)
2
If you are sure that n^4/n^3 is the best/worst case complexity of your algorithm, it is certainly correct to state that the algorithm is in O(n^4) and Omega(n^3).
Weather it makes sense to add this to the algorithms description, depends on your target audience:
- To present a generic algorithm to scientists, it is valuable, since it allows to compare the algorithm to others in terms of computational complexity. (Remember to clarify what n is)
- To present an algorithm tailored to a specific problem to practitioners, computational complexity might not be of interest. For example, your algorithm might still be worse than another, on average, if the n is usually small and never really big in the use case scenario.
Computational complexity provides a very abstract view on the algorithm. For theoretical considerations that is just what you want. In practice there may be many other properties that are much more important, because you can consider the problem specific factors.
0
It depends on what you do in each iteration. If you only perform at most a constant number of primitive computations in each iteration, then yes your running time is O(n^4). However, Theta(n^3) would mean that your running time has both the lower and upper bound n^3, which it does not. You can use Omega(n^3) to indicate the lower bound.
1