Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to add Big O and Big omega

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

like image 412
Mobi Avatar asked Sep 23 '12 16:09

Mobi


Video Answer


1 Answers

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.

like image 164
Zhuo Avatar answered Sep 23 '22 17:09

Zhuo