-4

I am searching for a standard way to identify running time complexity of a program. As described here, I am not searching for a solution for analyzing the same by looking at code, rather than through some other parameters at program runtime.

Consider a program which requires the user to convert a binary string to its decimal equivalent. The time complexity for such a program should be O(n) at worst, when each binary digit is processed at a time. With some intelligence, the running time can be reduced to O(n/4) (process 4 digits from the binary string at a time, assume that the binary string has 4k digits for all k=1,2,3...)

I wrote this program in C and used the time command and a function that uses gettimeoftheday (both) to calculate running time on a linux box having a 64 bit quad core processor (each core at 800 MHZ) under two categories:

  1. When system is under normal load (core usage 5-10%)
  2. When system is under heavy load (core usage 80-90%)

Following are the readings for O(n) algorithm, length of binary string is 100000, under normal load:

Time spent in User (ms) - 216
Time Spent in Kernel (ms) - 8
Timed using gettimeofday (ms) - 97

Following are the readings for O(n) algorithm, length of binary string is 200000, under high load:

Time spent in User (ms) - 400
Time Spent in Kernel (ms) - 48
Timed using gettimeofday (ms) - 190

What I am looking for:

  1. If I am using time command, which output should I consider? real, user or sys?
  2. Is there a standard method to calculate the running time of a program?
  3. Every time I execute these commands, I get a different reading. How many times should I sample so that the average will always be the same, given the code does not change.
  4. What if I want to use multiple threads and measure time in each thread by calling execve on such programs.

From the research I have done, I have not come across any standard approach. Also, whatever command / method I seem to use gives a me different output each time (I understand this is because of the context switches and cpu cycles). We can assume here that I can even do with a solution that is machine dependant.

Community
  • 1
  • 1
Cik
  • 381
  • 5
  • 16
  • The world is moving ahead and I am still procrastinating about my **Rivest Cormen** book.Sigh!! – Rüppell's Vulture May 15 '13 at 08:08
  • 2
    You found a way to reduce complexity from O(N) to O(N/4)? That's pretty impressive. And a sure sign that you should re-read those notes on what complexity is... – Kerrek SB May 15 '13 at 08:18
  • @KerrekSB I understand what you are trying to say. For all O(kN), complexity reduces to O(N). However, the granularity I am looking for compels me to use these notations – Cik May 15 '13 at 08:35
  • What about getting rusage with wait4 call? – Cik May 15 '13 at 08:36
  • 1
    I think you're misunderstanding the point made by Kerrek SB. Whether you operate on 1 item at a time or 4 items at a time, the complexity of the algorithm is still O(N) as you have to visit every item. – CadentOrange May 15 '13 at 08:40
  • @Cik: No. That's decidedly *not* the point. The very *meaning* of the word "complexity" is different from what you may be thinking. – Kerrek SB May 15 '13 at 08:41
  • @KerrekSB Maybe I will reframe my question: Can there be a correlation established between the time complexity and the runtime of a computer program? – Cik May 15 '13 at 08:47
  • @Cik: Yes. The complexity tells you how the runtime scales as a function of the input size. This isn't the same as exactly counting the runtime. It's more about the *relation* between running the program on 1000 elements and running it on 10000 elements. – Kerrek SB May 15 '13 at 08:52
  • You probably didn't find a way to do radix conversion in linear time. – tmyklebu May 15 '13 at 09:26
  • @tmyklebu http://stackoverflow.com/questions/4483189/convert-string-to-number-vice-versa-complexity ? – Cik May 15 '13 at 09:34
  • @Cik: No, really, you didn't. – tmyklebu May 15 '13 at 10:11
  • @Cik: you probably didn't take into account the complexity of (large) number arithmetics (if the bit string doesn't fit machine word) – user396672 May 15 '13 at 10:13

1 Answers1

0

To answer your questions:

  1. Depends on what your code is doing each component of the output of time may be significant. This question deals with what those components mean. If the code you're timing doesn't utilize system calls, calculating the "user" time is probably sufficient. I'd probably just use the "real" time.
  2. What's wrong with time? If you need better granularity (i.e. you just want to time a section of code instead of the entire program) you can always get the start time before the block of code you are profiling, run the code and then get the end time then calculate the difference to give you the runtime. NEVER use gettimeofday as the time does not monotonically increase. The system time can be changed by the administrator or an NTP process. You should use clock_gettime instead.
  3. To minimise the runtime differences from run to run, I would check that cpu frequency scaling is OFF especially if you're getting very wildly differing results. This has caught me out before.
  4. Once you start getting into multiple threads, you might want to start looking at a profiler. gprof is a good place to start.
Community
  • 1
  • 1
CadentOrange
  • 3,263
  • 1
  • 34
  • 52
  • What about using "you can always get the start time before the block of code you are profiling, run the code and then get the end time then calculate the difference to give you the runtime" in multiple threads instead of gprof? – Cik May 15 '13 at 08:32
  • You could do that of course and then log it to a file for each thread. You could then aggregate the results offline. – CadentOrange May 15 '13 at 08:35