5

If an algorithm has two sub algorithm, when it is best case for sub algorithm A1 to the given input, it is the worst case for sub algorithm A2. How could I find the overall algorithm complexity? Simply I mean Ω(N) + O(N)=? I know if the algorithms are in sequential executing order the over all complexity is O(N)+ O(N) and in nested order O(N)* O(N).

Please tell me in both cases, when in sequential and in nested order

Mobi
  • 645
  • 3
  • 6
  • 14
  • It is hard to tell what is your question. – barak1412 Sep 23 '12 at 17:02
  • Best case and worst case are different then big O and big Omega. Best case/Worst case/avg case are analysis of algorithms. The analysis results in a function. big O and big Omega are sets of functions. Each one of big O/big Omega/big Theta can be applied to each of best/worst/avg case analysis. I tried to explain this issue among others answering [this question](http://stackoverflow.com/questions/10376740/big-theta-notation/12338937#12338937) – amit Sep 23 '12 at 17:06
  • Simple, how to add runtime complexities of two algorithms? When one's complexity is big O and other's is big omega? Ω() + O()=? – Mobi Sep 23 '12 at 17:47

2 Answers2

6

Essentially Ω(N) + O(N)= Ω(N). Because O(N) means lower (or at most the same) order of Ω(N). When they are summed, the lower order can be omitted.

Zhuo
  • 86
  • 2
  • 1
    What is the + operator for *sets*? Omega and O are both sets of function, what is `SET + SET`? I am not familiar with a standard definition for it:| – amit Sep 23 '12 at 17:12
  • 2
    It's a slight abuse of notation. Ω(N) + O(N) = Ω(N) means if function f in Ω(N), and g in O(N), then f+g in Ω(N). – Zhuo Sep 23 '12 at 17:16
4

If your algorithm includes one operation which takes (for example) O(N) time, and another which takes O(N^2) time, then the overall complexity is O(N^2). There's no such thing as O(N^2 + N). The same goes for Ω(). This answers your question about "sequential executing order".

If your algorithm includes N operations, each of which takes O(N) time, then the overall complexity is O(N^2). The same goes for Ω(). You just multiply the polynomials, and take the term which grows most quickly with increasing N. This answers your question about "nested execution order".

Alex D
  • 29,755
  • 7
  • 80
  • 126