Question

How to derive mathematical equations on algorithm?

Answer 1

I have a an algorithm for taking in any input number and deriving the output. Following these steps I can calculate

f(x)=yf(x)=y

for any value of x, but it takes O(n^n) time to do manually. It appears to follow a pattern but not one that I can intuit easily.

Unfortunately I do not know where to even start for figuring out the actual function so that I can calculate the value more efficiently. Is there a way to take a data set of values from my algorithm and derive a function from it without knowing that it looks like a specific kind of curve?

In this specific instance the problem is

Find the sum of the digits of all the numbers from 1 to N (both ends included). For N = 10 the sum is 1+2+3+4+5+6+7+8+9+(1+0) = 46 For N = 11 the sum is 1+2+3+4+5+6+7+8+9+(1+0)+(1+1) = 48 For N = 12 the sum is 1+2+3+4+5+6+7+8+9+(1+0)+(1+1) +(1+2)= 51

and my naive algorithm loops through each number in the set, one by one.

I would appreciate the name of the technique used to derive a formula from a dataset like this, so that I can learn how to derive it myself