How to find big o of dependent loops and recursive functions?

Question

I want to be able to measure any code snippet time complexity. Is there a general rule or step by step approach to measure any big o (besides dominant term, removing constants and factors)? What math skills should I have, if so, what are the prerequisites for those skills? Also, what is enough for interviews?

Here is one of those:

int fun(int n) {
  int count = 0;
  for (i = n; i > 0; i /= 2) {
    for (j = 0; j < i; j++) {
      count += 1;
    }
  }
  return count;
}

I've read many algorithms books, but they're mathy and not beginner-friendly.

Answer 1

Unfortunately, there is no "one rule fits all" when determining the big O complexity of a dependent for loop or recursive function. When doing a complexity analysis, it generally involves breaking your code into smaller and smaller components, finding the complexities of those smaller components, and then combining them together. This can be easy for simple pieces of code, or very hard for more complex pieces of code (there are entire papers written on proving a big O upper bound for some advanced algorithms).

Dependent loops: For dependent loops, one thing you can do is find the complexity of the inner loop in terms of the outer loop's variable, and then do a summation over this.

For example, in your example code, the inner loop will run i times on each iteration of the outer loop. Since the outer loop is going to run iterations for i = n, n/2, n/4, ..., the big O complexity can be written as

Recursive Functions on the other hand, are just way too broad to give too much specific help. Sometimes you can find an upper bound on the number of times one function call will call itself, and the maximum depth of the recursion, which can give an exponential complexity. Other times, the recursive function is made with some kind of visited array (e.g. using some algorithm including memoization), where even the a single recursive call can call itself many, many times, the total number of times the function will run during the overall program is capped at some value.

tl;dr: In general, the best "rule" that you can apply is to keep finding complexities for smaller components of the code, and combining them, but there is no easy non-mathematical way to find the big O complexity for any code every time.