1

I have gone through a couple of examples in understanding the time complexity of a program using the operation count and step count technique but these examples are small and straight. However in real-world programming, if someone gives you the production or live code to find the worst case time complexity of it. How does one start analyzing it?

Is there any technique or thumb rules for analyzing the program? say I have a function as shown below that has if and for conditions. For some values of n, it goes deep but for some values, it does not. So maximum number of operations is the worst case and the minimum number of operations is the best case. How can we know when do maximum operations occur if we have this kind of conditional statement? (Other functions can go much deeper conditional and not the loops)

int l = 0;
while (l <= n){
  int m = l + (n-l)/2; 
     
  if (arr[m] == x) return;   
  if (arr[m] < x) l = m + 1;  
  else n = m - 1;  
}

How does one calculate the worst and best case by looking at the above code? Do the perform step count for the above program and by substituting n = 1 till 20 and get some values and then trying to derive the function? I would like to know how do people analyze time complexity for existing code when they have this kind of branching statements.

Step by Step analysis or Set of statements to follow to solve the above problem would be greatly helpful.

user3205479
  • 1,443
  • 1
  • 17
  • 41
  • 1
    The same way you analyse any algorithm: examine the control structures and the variables governing them. In your example, each loop iteration either updates `l` or `n` by setting it to `m+1` or `m-1`, and `m` is the average of `l` and `n`, so this is a logarithmic function. (It is, in fact, a binary search, but the above analysis doesn't need to know the algorithm to determine its complexity.) – Welbog Jan 19 '21 at 13:02

1 Answers1

2

As each time half of the n is added to m and the loop will be continued by increasing a unit of l or changing the value of the n to the m-1 the following scenario can give the maximum operation:

In each iteration, the `else` part is happened and set `n` to `m-1`.

Let see what is happened for this case. As each time n is dividend by 2, and l is keeping 0, after O(log(n)) iteration, l == n.

Therefore, the time complexity of the loop is O(log(n)).

Notice that other cases can increase l faster towards n. For example, if l = m + 1 it means that l = (n-1)/2, and in the next iteration, m will be increased to n-1. Hence, just 2 iteration we will have to reach to the end of the loop.

OmG
  • 18,337
  • 10
  • 57
  • 90