Codesnippet with runtime t(n) ∈ Θ(n^3/2 )

Question

I'm trying to solve an excercise, where I have to write a codesnippet with a t(n) ∈ Θ(n^3/2) runtime.

I'm allowed to use recursions, addition, subtraction, division of integers by 2, for loops, if statements, <, >, == as well as if- and return-statements.

To get a runtime of t(n) ∈ Θ(n^3) I'd have to just use 3 for-loops, also I think there was this rule, where by using if-statements, the runtime becomes logarithmic. I have hoever no Idea on how to get a runtime of t(n) ∈ Θ(n^3/2).

I'd be really glad if someone could provide some advice. Thanks :)

Answer 1

Here is code snippet to find the divisors factors of all numbers from 2 to N done in O(N^3/2).

    for(int i=2;i<=N;i++)
    {
        for(j=2;j*j<=i;j++)
        {
            if(i%j==0)
            {
                printf("another non-trivial divisor pair for %d is %d,%d",i,j,i/j); 
            }
        }
    }

Outer loop is O(N) and inner is O(N^1/2).