# What is the computational complexity of a brute force perfect numbers finder algorithm?

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);
}

-
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

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.