finding complexity in an if clause

Question

assume that I have an if clause

if (!f(x))
{
   g(x);
}

the complexity of f(x) = O(x^3) and complexity of g(x) = O(x^2). In this case what is the overall complexity ? O(x^5) ? or O(x^3) ?

I wanted to increase my question sizes.

while(z(x))
{
  for(p(x))
  {
     if (!f(x))
     {
       g(x);
     }
  }
}

where, z(x) = O(x^5), p(x) = O(x),f(x) = O(x^3), g(x) = O(x^2)

possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Scott Mermelstein, Jan 20 '14 at 22:31
You can reduce that further. When dealing with Big O, if there are added terms, you can simply keep the most expensive one. And then you can combine all your multiplies. — Scott Mermelstein, Jan 20 '14 at 22:52

score 5 · Answer 1 · answered Jan 20 '14 at 21:57

5

The total complexity is O(x³) because you have an x³ operation followed (possibly) by an x² operation. The former dominates the latter: O(x³) + O(x²) = O(x³).

answered Jan 20 '14 at 21:57

TypeIA

16,916
1
38
52

thanx for the answer. what about if clause has if(f(x) && h(x)){g(x)}, where f(x)=O(x^3) and h(x)=O(x^2) and g(x)=O(x^2). – zaratushtra Jan 20 '14 at 22:00
1

@zaratushtra Same result for the same reasons; 3 sequential operations, and the x^3 term dominates. – TypeIA Jan 20 '14 at 23:01

score 0 · Answer 2 · answered Jan 21 '14 at 07:52

You need to remember that 'O' complexity exhibit upper bound for that algorithm. Think wrt worst case scenario (upper bound).

In your first case, if your 'if' condition succeed complexity would be O(x3) + O(x2), which will be equivalent to O(x3). since if condition will execute once so you try to add up orders and highest order will define the upper bound.

Now in your second example. Loops will multiply their order with code covered by them. So complexity would be O(x5)O(x)(O(x3) + O(X2)). The upper bound of which come out to be O(X8).

score 0 · Answer 3 · answered Jan 21 '14 at 14:22

For first example it is O(x^3) because O(x^3) dominates over O(x^2) in big-O notation. Second example O(infinity) because you dont know when the while loop will end, it may go on for ever so big-O is O(infinity) . lower bound for it is O(x^5) because it might get false in first iteration of while

finding complexity in an if clause

3 Answers3