Big-O of these nested loops

There are many questions here like "Big-O nested loops" here on stackoverflow (and answers).

However, you will receive a response from me. But first there is a problem with the notation: You marked this question as java. In the code, I see something like 2ⁿ

or n²

. In java it meansxor

, but I think you meant it Math.pow(2,n)

instead, so for this answer I will treat it as a cardinality operator.

• int sum=0;
  for(int i=0; i < n^2; i++) {             // outer loop
      for(int j = n-1; j >= n-1-i; j–-) {  // inner loop
          sum = i+j;                       // inner operations
          System.out.println(sum);
      }
  }
  
        
  
          
          
          
        
  
      

  The inner operations are done in O(1)
  
  , so I just count how often they are called.

  • The outer loop runs n²
    
    once.
  • for each i
    
    (from the outer loop) the inner loop starts i
    
    times.

  You get everything 0+1+...+(n²-1)+n² = n²(n²+1)/2
  
  . It's in Θ(n⁴)
  
  .

• int sum=0;
  for(int i=1; i <= 2^n; i=i*2) {           // outer loop
      for(int j=0; j <= log(i); j++) {      // inner loop
          sum = i+j;                        // inner operations
          System.out.println(sum); 
      }
  }
  
        
  
          
          
          
        
  
      

  • The outer loop runs n
    
    times since 2⋅2⋅2⋅...⋅2
    
    ( n
    
    times) is 2 ⁿ .
  • The inner loop runs k
    
    once for every i = 2 ^k (1 ≤ k ≤ n) if the base of the logarithm is 2.

  In total, you get 1+2+3+...+n-1+n = n(n+1)/2
  
  . It's in Θ(n²)
  
  .

• int sum = 0; int k = 23;
  for(int i=k; i <= 2^(n−k); i=i*2) {          // outer loop
      for(int j=2^(i−k); j < 2^(i+k); j=j*2) { // inner loop
          sum = i+j;                           // inner operations 
          System.out.println(sum);             
      }
  }
  
        
  
          
          
          
        
  
      

  • In the outer loop, it is executed m
    
    with the m
    
    minimum that is executed . This can be written as . must be positiv (otherwise the outer loop will run forever). Assuming limited (canstants are also in ), also limited .k⋅2m > 2n-k

k⋅2k⋅2m > 2n

k

k

O(n)

O(n)

m

O(n)
    
    
  • The inner loop always runs 2⋅k
    
    once, no matter what i
    
    or n
    
    . It is in O(1)
    
    for a constant k
    
    and in O(n)
    
    for a k
    
    bounded O(n)
    
    .

  In total you get O(n)
  
  for the constant k
  
  and O(n²)
  
  for a k
  
  in O(n)
  
  .

• int sum=0;
  for(int i=2n; i>=1; i=i/2) {       // outer loop
      for(int j=i; j>=1; j=j/2) {    // inner loop
          sum = i+j;                 // inner operations
          System.out.println(sum);
      }
  }
  
        
  
          
          
          
        
  
      

  • The outer loop starts log(n)
    
    once, as in case 2 (vice versa)
  • The inner loop starts j
    
    times for (basically) every power 2 between 1
    
    and 2n
    
    .

  By assuming (means ) you get the total . So this is in . This is also the case for n not degree 2.n = 2k

log(n) = k

2k+1+2k+2k-1+...+22+21+20=2k+2-1=4n-1

O(n)