Asymptotic Analysis - Triple Loop - k starts from j^2

Question

What is the time complexity of this program?

for i = 1 to n

    for j = i to n

      for k = j*j to n

         sum++;

Answer 1

I believe it's O(n²) , and it complies with observed result.

/*******Updated Analysis**********/

As innermost loop only executes on the conditions that i ≦  n^0.5 and j ≦ n^0.5, the original pseudocode can be divided to two parts. 
 

Part 1:
for i = 1 to n^0.5

    for j = i to n^0.5

      for k = j*j to n 

         sum++;

Part 2:

for i = 1 to n

    for j = n^0.5 to n

      for k = j*j to n //will only run once and end loop, hence O(1) 

For the first part 

The innermost loop (sum++) execute on every combination that satisfies 1 ≦ i ≦ j ≦ k^0.5 ≦ n^0.5

Hence the total count should be something like n^0.5 * n^0.5 * n giving the time complexity O(n²)

And the second part is clearly O(n²), hence the original algorithm also run at O(n²).

Answer 2

Please provide more information - at least 12 characters

Comments

Good job, TA!

Answer 3

Since the professor suggested that someone try to help prove this programmatically, I've taken the liberty to show that this algorithm runs in O(n^2) time:

public class Algorithm {

    public static void main(String[] args) {
        int sum = 0;
        int n = 100000;

        for (int i = 1; i < n; i++) {
            for (int j = i; j < n; j++) {
                for (int k = j * j; k < n; k++) {
                    sum++;
                }
            }
        }

        System.out.println("complexity: " + sum);
    }
}

Output:

n = 10
sum = 24

n = 100
sum = 2475

n = 1000
sum = 249984

n = 10000
sum = 24997500

Answer 4

Is it simply O(n^2.5) ?

Comments

Ethan, perhaps it may be easier to just run the algorithm on n say 100, 1000 and confirm if your hypothesis matches the observed result?

Answer 5

I think it's n^2 log log n.

Comments

Gouri, how can we prove it is n^2 log log n?

---

Sorry, I was wrong. I mistakenly considered j*j as condition.

Answer 6

This is my try= O(n^3)

Comments

Amal, how about simply run this algorithm in your favorite IDE (like Eclipse) and see how the time taken taken for n = 1000  and n = 100 compare.

---

I'll try it!