2

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).

  • typo in 2nd block : x[i] == target/. What is exactly your question ? Does a method execution always depend on the big O ?, That the whole purpose of the big O. – Walfrat Apr 6 '17 at 11:41
  • @Walfrat I'm new here so I maybe not good to formulate my question well. I mean when a method executes we approximate the execution time with the help of Big O. To approximate the time we look at how money loop it has, My question is if it is so that the approximated time is proportional to the loop quantity. – Adam Apr 6 '17 at 11:56
  • 1
    Basically, yes. However this happen for recursive function to (which may be rewriten by the compiler as loops when he can). Big O is just here to tell you if the time taken by the method depends of you data's size, and if so, how much( linear, quadaratic,...). Loops are basically THE basic operaion that takes longer if you have more data. – Walfrat Apr 6 '17 at 12:10
  • 1
    But maybe you're asking about others factor than data size that can make grow the time of exeuction? If so, any sort of IO (disk, network, ...) increase the time specially if you handle them badly. – Walfrat Apr 6 '17 at 12:12
4

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 nnumber 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 log2n 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.

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.