Analyzing time complexity of a function written in C

Question

I was implementing Longest Common Subsequence problem in C. I wish to compare the time taken for execution of recursive version of the solution and dynamic programming version. How can I find the time taken for running the LCS function in both versions for various inputs? Also can I use SciPy to plot these values on a graph and infer the time complexity?

Thanks in advance,

Razor

Answer 1

For the second part of your question: the short answer is yes, you can. You need to get the two data sets (one for each solution) in a format that is convenient to parse with from Python. Something like:

x y z

on each line, where x is the sequence length, y is the time taken by the dynamic solution, z is the time taken by the recursive solution

Then, in Python:

# Load these from your data sets.
sequence_lengths = ...
recursive_times  = ...
dynamic_times    = ...

import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
p1 = ax.plot(sequence_lengths, recursive_times, 'r', linewidth=2)
p2 = ax.plot(sequence_lengths, dynamic_times,   'b', linewidth=2)

plt.xlabel('Sequence length')
plt.ylabel('Time')
plt.title('LCS timing')
plt.grid(True)
plt.show()

Answer 2

The simplest way to account processor time is to use the clock() function from time.h:

clock_t start, elapsed;

start = clock();
run_test();
elapsed = clock() - start;

printf("Elapsed clock cycles: %ld\n", (long)elapsed);

Since you are simply comparing different implementations, you don't need to convert the clocks into real time units.

Answer 3

There are various ways to do it. One of the simpler is to find some code that does high resolution (microsecond or smaller) timing of intervals. Wrap calls to the start-timer and stop-timer functions around the call to the LCS function, then print the resulting elapsed time:

#include "timer.h"

Clock clk;
char elapsed[32];

clk_start(&clk);
lcs_recursive();
clk_stop(&clk);
printf("Elapsed time (recursive): %s\n",
       clk_elapsed_us(&clk, elapsed, sizeof(elapsed)));

Similarly for the lcs_dynamic() function.

If the time for a single iteration is too small, then wrap a loop around the function. I usually put the timing code into a function, and then call that a few times to get consistent results.

I can point you to the package illustrated.

Yes, you could feed the results, with care, into a graphing package such as SciPy. Clearly, you'd have to parameterize the test size, and time the code several times at each size.