1
$\begingroup$

QUESTION

does CPU time reflect Big O time complexity?

WHAT I MADE

I implemented two Fibonacci functions in C programming language. The former has recursive behaviour while the latter has iterative behaviour.

I found out that the worst case scenario for the recursive version is exponential time (i.e. $2^n$) and linear time for the iterative one - since I have a simple loop within.

I then computed the CPU time for both the version using the time.h C library.

WHAT I EXPECT

I expect those CPU values to be somehow related with that time complexity. Generally speaking, I expect way larger CPU times for the recursive version.

WHAT I GOT

I got the foregoing plot using MATLAB (that is a loglog plot of cpu times as function of $n$).

this plot

Seems like the CPU time for the recursive function has an exponential behaviour - that is what I was expecting. Though, I'm not completely sure about CPU time for the iterative version since that function does not look like this one (section log-log graphs).

I'd like to answer myself without doubts but I'm quite newbie.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ First, you need to understand exactly what you mean by "time complexity". Which quantity did you analyse? Which machine model did you use? Then, you need to inspect your experiment: you can not really expect to observe asymptotic properties with finite sets of measurement, but experience shows that you usually see something if the input sizes are large enough. $\endgroup$
    – Raphael
    Commented Dec 2, 2016 at 19:02
  • $\begingroup$ @Raphael thanks for having pointed it out. I may use "time complexity" improperly. What I'm trying to do is to analyse some CPU times (therefore, sec). I was asked if I could see any relation between the time complexity, that I measured using Big O, and these durations. Probably I did not take a large enough input, and I did not take into account my machine model. It's quite hard at the very beginning! $\endgroup$
    – Mattia Paterna
    Commented Dec 2, 2016 at 21:27
  • $\begingroup$ The other points I raise are not moot. For instance, if you analyse, say, Quicksort on a Turing machine, you will not get $O(n \log n)$ average-case "complexity", but that's what you will observe on real machines. $\endgroup$
    – Raphael
    Commented Dec 3, 2016 at 11:22
  • $\begingroup$ The naive recursive implementation of the Fibonacci function takes O (fib (n)), which is a lot faster than O (2^n). $\endgroup$
    – gnasher729
    Commented Sep 24, 2017 at 14:42

1 Answer 1

Reset to default
3
$\begingroup$

There are really two questions here:

  1. How does CPU time relate to time complexity?

  2. Can you use a plot of CPU time to understand time complexity?

Let me answer each in turn.

Time complexity

Time complexity refers to the total time it takes for the algorithm to finish.

If by "CPU time" you just mean the time it took for this particular program to run, excluding the time for other programs or the operating system, then yes, these are the same.

If by "CPU time" you meant the time spent on computation but not time spent on I/O, then it might or might not match what is meant by time complexity. In practice, I/O is often slower than computation -- maybe by a significant factor. Normally, in theoretical work where we measure time complexity, we don't try to account for that distinction, as it's "only a constant factor".

The plot heuristic

Plotting the running time as a function of the size of the input can definitely be a useful heuristic to form an informed guess about what the asymptotic time complexity of the an algorithm is. It's often a good guide. However, be warned that it is not 100% reliable: there are some cases where it can be misleading.

I'd like to refer you to the following three questions for more on this topic:

Bottom line

In summary: yes, basically, plotting CPU time as a function of input size can be a helpful way to assess asymptotic time complexity, as long as you keep in mind the caveats.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Does this answer the specific question? $\endgroup$
    – Andrew
    Commented Dec 2, 2016 at 18:53
  • $\begingroup$ @AndrewMacFie, thanks for the poke! I edited to add a summary at the end that more directly answers the question. Does that look better? $\endgroup$
    – D.W. ♦
    Commented Dec 2, 2016 at 18:57
  • $\begingroup$ @D.W. I'm profoundly thankful. Some week ago, I've been pointed out the difference between CPU time and wall time. In this case, I just keep track of the time that the algorithm only takes for different n. $\endgroup$
    – Mattia Paterna
    Commented Dec 2, 2016 at 21:44
  • $\begingroup$ @D.W. I just have another question: when using I/O, you mean passing the arguments to the function or some operations like cin or cout? Maybe I'm digging too deep. $\endgroup$
    – Mattia Paterna
    Commented Dec 2, 2016 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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