CODEWITHSUNDEEP
algorithm
cheroz
cheroz

Reputation: 127

Calculating the time complexity of this algorithm

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?

Upvotes: 2

Views: 90

Answers (2)

user1196549
user1196549

Reputation:

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).

Upvotes: 2

Rob
Rob

Reputation: 2654

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)

Upvotes: 1

Related Questions