Calculating the time complexity of this algorithm

Question

I'm trying to calculate the time complexity of this algorithm that determines if a positive integer N can be expressed as x^y. The algorithm's author is Vaibhav Gupta.

// Returns true if n can be written as x^y
bool isPower(unsigned int n)
{
    // Base case
    if (n <= 1) return true;

    // Try all numbers from 2 to sqrt(n) as base
    for (int x=2; x<=sqrt(n); x++)
    {
        unsigned  p = x;

        // Keep multiplying p with x while is smaller
        // than or equal to x
        while (p <= n)
        {
            p *= x;
            if (p == n)
                return true;
        }
    }
    return false;
}

The author says that this algorithm is an optimized version of the first one which is:

// Returns true if n can be written as x^y
bool isPower(unsigned n)
{
    if (n==1)  return true;

    // Try all numbers from 2 to sqrt(n) as base
    for (int x=2; x<=sqrt(n); x++)
    {
        unsigned y = 2;
        unsigned p = pow(x, y);

        // Keep increasing y while power 'p' is smaller
        // than n. 
        while (p<=n && p>0)
        {
            if (p==n)
                return true;
            y++;
            p = pow(x, y);
         }
    }
    return false;
}

Does this first one has a different time complexity since he uses the pow function?

For me this is very strange that there are no check if (n % x != 0) continue; right before while. Is there any reason to avoid this optimization? — Ilya
– Ilya, Commented Apr 8, 2016 at 12:35
@ilya - The question is not about that. It is about the complexity of the algorithm as written. — Stephen C
– Stephen C, Commented Apr 8, 2016 at 12:36

score 2 · Accepted Answer · 2016-04-08 13:37:49Z

2

When it returns false, the algorithm tries increasing powers of all integers x, until they exceed n. The search stops after x = √n has been tried.

So for a rough evaluation, evaluating the powers until x^d = n takes about log n/log x multiplies, and is repeated from x=2 to x=√n.

Hence the complexity is like

log n.Sum(x=2 to √n)1/log x

which is uneasy to estimate, but O(log n.√n) and Ω(√n).

The pow version takes log d multiplies instead of 1 to compute a power, provided it does so by repeated squarings. As d = log n/log x, the complexity is like

log n.Sum(x=2 to √n)(log log n - log log x)/log x

even harder to estimate, but O(log n.log log n.√n) and Ω(√n).

For the range of n covered by the int type, you can expect the pow version to be between one time and five times slower (unless the pow function has a big overhead).

edited Apr 8, 2016 at 13:37

answered Apr 8, 2016 at 13:22

user1196549

Sign up to request clarification or add additional context in comments.

6 Comments

Paul Hankin Over a year ago

Sum(x=2 to √n)1/log x ~= √n / log(√n) so the complexity is O(√n). (mathforum.org/kb/message.jspa?messageID=89138 for details of the sum).

user1196549 Over a year ago

@PaulHankin: thanks. That confirms O(log n.√n) and Ω(√n). :)

Paul Hankin Over a year ago

I think it's nice to find a tight bound here, because it motivates the more careful analysis that you've done here, and shows that the naive approach of approximation in the other answer gives the wrong answer. Anyway, I upvoted :)

user1196549 Over a year ago

@PaulHankin: if I am right, the complexity of the slower algorithm can be addressed by the same method. The extra factor should be log log n, or lower.

Paul Hankin Over a year ago

Yes, the second algorithm is somewhere between O(√n) and O(√n log log n), and the exact expression isn't of any practical value given how slowly log log n grows.

|

Rob · Accepted Answer · 2016-04-08 12:38:38Z

1

Looks to me like the outer loop is square root of n, and the inner loops are in the order of log n (since the number grows exponentially) so your complexity should be something in the tune of

  O(sqrt(n)*log n)

answered Apr 8, 2016 at 12:38

Rob

2,6292 gold badges24 silver badges30 bronze badges

4 Comments

Paul Hankin Over a year ago

The inner loop runs log_x(n) times (log_x being log base x). Why is it valid to ignore the changing base when doing the summation?

Rob Over a year ago

@PaulHankin Yes it is because you can turn any log base A of x into a log base b of x by simply multiplying by a constant mathwords.com/c/change_of_base_formula.htm and constant multipliers go away with big-O notation :)

Rob Over a year ago

@PaulHankin I answered a similar question a while back :) stackoverflow.com/questions/6314337/…

Paul Hankin Over a year ago

@Rob I see what you mean, but the complexity involves summing over these changing bases, and the method is incorrect (and produces the wrong answer overall). Yves' answer below uses a correct approach.

Collectives™ on Stack Overflow

Calculating the time complexity of this algorithm

2 Answers 2

6 Comments

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related