Big-O of These Nested Loops

Question

I'm pretty new to the Big-O field, so bear with me here. I have been searching about it as much as I could but I still need a lot of work to fully understand it.
I came across these nested for loops in a practicing exercises and there wasn't any solutions and they seem complicated. So, any help would be appreciated.

1)

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

Big-O = ?

2)

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

Big-O = ?

3)

int sum = 0; int k = 23;
for(int i=k; i <= 2^(n−k); i=i*2) { // log(n)
    for(int j=2^(i−k); j < 2^(i+k); j=j*2) { // log(log(n)) ?
        sum = i+j; // log(log(n)) ?
        System.out.println(sum); // log(log(n)) ?
    }
}

Big-O = ?

4)

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

Big-O = ?

---

EDIT:
- Corrected #4. Sorry for the mess up.
- Base of the log is 2.
- The ^ here means "to the power", not xor.

Answer 1

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

However, you will get an answer from me. But first there is a notation problem: You tagged this question as java. In the code I see something like 2ⁿ or n². In java this means xor, but I think you meant Math.pow(2,n) instead, so for this answer I will treat it as a power operator.

1. 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 runs in O(1), so I just counting how often they are called.

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

   In total you get 0+1+...+(n²-1)+n² = n²(n²+1)/2. This is in Θ(n⁴).

2. 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) equals 2ⁿ.
   • The inner loop runs k times for each i=2^k (1 ≤ k ≤ n), assuming the base of the logarithm is 2.

   In total you get 1+2+3+...+n-1+n = n(n+1)/2. This is in Θ(n²).

3. 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);             
       }
   }
   

   • The outer loop runs m times with m minimal such that k⋅2m > 2n-k holds. This can be written as k⋅2k⋅2m > 2n. k has to be positiv (otherwise the outer loop will run forever). Assuming k is bounded by O(n) (canstants are also in O(n)), m is also bounded by O(n).
   • The inner loop runs always 2⋅k times, no matter what i or n is. This is in O(1) for a constant k and in O(n) for a k bounded by O(n).

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

4. 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 runs log(n) times just like in case 2 (the other way around)
   • The inner loop runs j times for (basicly) each power of 2 between 1 and 2n.

   Assuming n = 2k (means log(n) = k) you get in total
   2k+1+2k+2k-1+...+22+21+20=2k+2-1=4n-1. So this in in O(n). This also holds for n not a power of 2.

Answer 2

Methodically finding a solution for your iterative algorithms using Sigma notation:

---

Using base 2 for the log below:

---

---