In a certain problem, the complexity of my algorithm is O(n*sum_of_factors(n)), I want to get a simple bound for the complexity. Obviously one bound is O(n^3), since there can be n factors each with maximum value n, a better bound is O(n^2*sqrt(n)) since a number can have 2*sqrt(n) factors.
Please help me to give a better bound in terms of simpler functions of n, (simple is defined here as stuff you can find on a standard scientific calculator).
https://en.wikipedia.org/wiki/Divisor_function#Growth_rate
It seems that your runtime could be loosely bounded by O(N^2 * log(N))
Sum of factors could be represented as something like this, for a given number N:
N/1 + N/2 + N/3 .... N/N
This sum can be represented as N * H(N), where H is a sequence known as the harmonic numbers. They are known to approximate the natural logarithm function, so this sum can instead be swapped for N * log(N). This is still a pessimistic upper bound, since clearly the divisors can't go all the way from 1 to N. The only way you would have all the terms N/i where i goes from 1 to N is if N is a common multiple of all the numbers from 1 to N, which would limit your size of N.