Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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)

share|improve this question
    
To judge weather this is correct, I'd need to see the algorithm. Weather or not it is useful, depends on what you want to do. Talking about Complexity has its uses, e.g., it will tell you about scalability. So what's your goal? –  Sven Jan 27 at 8:54
    
@salsolatragus The "best case" and "worst case" analysis is correct and the algorithm is optimal. I'm asking if, having those "best case" and "worst case", it is correct to assert that the complexity of the algorithm is in \Omega and \BigO. And if it's correct would it be useful to know both \Omega and \BigO in the algorithm description? –  HAL9000 Jan 27 at 9:01

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
Thanks I agree with you. –  HAL9000 Jan 29 at 9:22

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.

share|improve this answer
    
Thanks, I'm an idiot, I wrote Theta here but I intended to write Omega, I fix the question. –  HAL9000 Jan 27 at 9:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.