Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A loop goes thru all numbers from one to N to find perfect numbers. For each number in the range, it checks all numbers less than it to see if it's a divisor by modding it by the number and checking if the result is zero. It keeps track of the running total of the divisors, and stops if the running total gets higher than the number being checked. What's the complexity of this? I think it's something exponential...Here's the C++ code I wrote to do it:

for(int i = 0; i < nums_to_check.size(); i++)
{
    number = nums_to_check[i];
    running_total = 0;
    for(unsigned long long j = number-1; j > 0; j--)
    {
        if(number % j == 0)
        {
            running_total += j;
            if(running_total > number)
                break;
        }
    }

    if(running_total == number)
        perfect_numbers.push_back(number);
}
share|improve this question
    
I'll not comment on the efficiency of this algorithm, which is horrible given what is known about perfect numbers. However I always write a decreasing loop in C++, like your inner loop, as "for(unsigned long long j = number; j-->1; )". This is both more clearly the opposite of "for(... j=1; j<number; ++j)", but most importantly continues to work correctly if the lower limit were not 1 but 0, as it often is. With your style that would fail (never terminate) when using an unsigned loop variable. In addition j-->0 looks very cute, once you get used to it. –  Marc van Leeuwen Mar 15 '12 at 9:54
    
@marcvanleeuwen i'm aware that a brute force approach is ridiculous, but it's for an assignment that isn't about the perfect numbers. it's just a filler. and yeah i was changing a lot of things in the code before i posted it. it's a rough rough draft. –  Marty Mar 15 '12 at 10:11
add comment

1 Answer 1

up vote 0 down vote accepted

Looking at the structure of this algorithm, you will find that it has two nested for loops. The outer loop runs exactly nums_to_check.size() times, so it is sufficient to multiply the average time complexity of the inner loop by that number.

Now, the inner loop obviously runs at most number-1 times, so its run-time is bounded by the maximum value occuring in nums_to_check times a constant. Therefore, a trivial upper bound for the run-time of this algorithm is $O(|N| \cdot \max N)$, where $N$ denotes the multi-set of numbers in nums_to_check (the order of numbers in $N$ is actually irrelevant).

If you allow huge numbers in $N$ (e.g., using a BigInteger class or the like), you may have to factor in bit complexity for these operations, but this depends on the chosen complexity measure (unit complexity vs. bit complexity). On the other hand, if you are content using bounded integers (e.g., unsigned long long), unit complexity is within a constant factor of bit complexity, so it does not make any difference for complexity analysis.

Finally, you may get a better estimate by analyzing the probability that the inner loop is terminated early.

share|improve this answer
    
Since the first half of the inner loop is entirely useless, it will never terminate early enough to improve on its worst-case complexity. –  Marc van Leeuwen Mar 15 '12 at 10:19
    
True, but my argument will still hold even if the algorithm is changed to work with a useful version of the loop (i.e., counting from 1 to number), where early termination for abundant numbers will occur. –  Johannes Kloos Mar 15 '12 at 11:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.