Tips for Calculating Time Complexity with Divisor Counts

\ f\left(N\right)\ =\ N의\ 약수의\ 개수

for (int i=0; i<f(N); i++)
    for (int j=0; j<f(N); j++)

O\left(\sqrt{N}^2\right)

I'm not sure this is the exact time complexity of the algorithm.
But I can guarantee it runs faster than O(root(N)^2).

Let's think about why.
First, let's count the divisors.

To find the divisors of N, divide by everything from 1 to root(N),
and whenever N divides evenly, store both the divisor and the quotient. (store two at a time)

So the number of divisors is always at most 2 * root(N).
Therefore the following holds.

f\left(N\right)\ \le \ 2\sqrt{N}

Now if we plug 2*root(N) into the algorithm, we can see the following holds.

O\left(2\sqrt{N}\cdot 2\sqrt{N}\right)\ =\ O\left(\sqrt{N}^2\right)

Comments