Is a procedure's complexity a function of how many nested loops it has?

Question

Take this example

  public static boolean uniqueNumbers(int[] x){
       for(int i = 0; i <x.length; i++){
          for(int j = 0; j <x.length; j++){
              if(i != j && x[i] == x[j])
                  return false;
        }    
    }
    return true;
  }

The loop body will execute x.length times for loop with index i. The inner loop with index j will also execute x.length times, giving a complexity of O(n^2) where n = x.length.

As another example

public static int targetSearch(int[] x, int target){
     for(int i = 0; i < x.length; i++){
        if(x[i] == target)
          return i;
     }
     return -1;
 }

The loop body will execute x.length times since it has only one loop giving a complexity of O(n).

Answer 1

Big O notation is used to get an idea for what will happen to execution time as number of items to process increases. Loops are the easiest example of how something increases multiplicatively. Simply counting loops to get a big O of n^{number of nested loops} won't always work.

Here's a trival example of a big O n! program

void nFacRuntimeFunc(int n) {
  for(int i=0; i<n; i++) {
    nFacRuntimeFunc(n-1);
  }
}

there are also algorithms like binary search that appear to have nested loops, but is actually big O log₂n because the loops are dividing your input with each iteration.

In addition to just naively counting loops you need to take into account what the loops are doing to change the size of the next iteration.

Answer 2

Most of the time, a method's execution time (in big O) depend on the amount if of loops it has. But not always.

Trivial counter example:

for(i=1...n)
   for(j=1...n)
       i *= 2

This is obviously O(n) since the outer loop will in fact be executed only once. This may be a trivial example but there are many algorithms where depending on how it's iterated and other internal conditions, lead to lower bounds than the strict amount of loops.