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.

I made a program with two functions to calculate factorial. The first uses loops to made de calculations, and the second uses recursive calls to get the same result.

The same program measures the time that the computer spends to use those functions and came out with those results in milliseconds:

        1!  2!  3!  4!  5!  6!  7!  8!  9!  10! 15! 19! 20!
Loop    3   4   7   11  15  19  23  30  32  36  62  78  82
Rec.    3   8   14  21  29  33  40  46  53  59  94  132 145

How can I come out with the two equations that I could put F as the factorial number and then the X came with the milliseconds spent to each method of calculation?

All I know is that the loop equation should be linear and the recursive should be exponential.

There is a question StackOverflow about the creation of that code and time measure.

share|improve this question
1  
You see approximately a factor two increase in execution time because the recursive implementation has to spend time unwinding the stack when the computation is done. –  kahen Feb 11 '13 at 15:00
1  
?? the recursive one should be linear as well, shouldn't it? Anyway, do you know about linear regression? –  Hagen von Eitzen Feb 11 '13 at 15:00
    
@HagenvonEitzen. No, Not yet... –  EASI Feb 11 '13 at 15:03

2 Answers 2

up vote 2 down vote accepted
+25

For the loop series the linear regression gives the following approximation: $$ X = 4.37 \cdot F -5.68 $$

Also the recursive series is best approximated with a linear function: $$ X = 7.32 \cdot F -9.28 $$

Here are the plot of your data (in blue) and regression functions (in red).

enter image description here

enter image description here

share|improve this answer

You need to put each function call on its own thread and then start a monitoring of each thread individually. I don't know what language you're using, so I don't know what kind of code to show you. In some Java-ish pseudo-code, you might have something like:
Runnable runner1 = new Runnable() { public void run() { f1(); } };
Runnable runner 2 = ...
long f1Time = getTime(); executor.submit(runner1); f1Time = getTime() - f1Time;
long f2Time = ...
System.out.println( f1Time + "\n" f2Time );

And then the same for f2(). You would then have two outputs on the screen for each function. The time elapsed (delta) would be the time of that particular function. This assuming you have setup an ExecutorService. There is also an option to hold until you tell all threads to go simultaneously if that works better for you. I know you didn't ask about Java, but that's one way. See: ExecutorService.

share|improve this answer
    
I executed them separated –  EASI Jun 24 '13 at 12:27

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.