2

If the time complexity of my program is,say O(n^2),How do I express running time in terms of seconds for a large value of n,10^6 ?

I need a rough estimate of that to know if optimization is required or I can proceed with my code....Time Limit is 0.6 seconds

The question is not about calculation of Time complexity....It's about estimation of running time from Time complexity

autistic
  • 1
  • 3
  • 35
  • 80
rsd_unleashed
  • 151
  • 2
  • 12
  • 5
    There is no way to reach out an execution time estimation using Big O notation – Steephen Jun 03 '15 at 11:50
  • It's depends on your machine - how many instruction it can completes per seconds. – Razib Jun 03 '15 at 11:51
  • 1
    possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Levi Jun 03 '15 at 11:51
  • @Steephen: Not even Rough estimate?Then what is the way out....Should we submit it and optimize it if we get a TLE? – rsd_unleashed Jun 03 '15 at 11:52
  • 2
    @rsd_unleashed you should execute and measure the time and optimize – Steephen Jun 03 '15 at 11:54
  • 4
    Big O notation tells you how a code scales, not how long it will take. That is, an O(n^2) algorithm will take 4 times longer to complete a problem where n is twice as big. It doesn't tell you anything about how long it takes for a given n, because there are too many other factors involved. Aside from creating a test case and measuring it yourself, there is no way to determine how long it will take. –  Jun 03 '15 at 11:55
  • How can we tell you what `10^6 * some_time_constant` is if you haven't told us what `some_time_constant` is? – autistic Jun 03 '15 at 11:55
  • Because big-O notation eliminates constant factors, there is no way to get an estimate of running time from O(n^2) alone. You need to have at least a few data points of your running algorithm to get even a very rough approximation. You can do this by implementing the core portion of your algorithm, and running it on your hardware with a small data sample. – Sergey Kalinichenko Jun 03 '15 at 11:56
  • Depends on how big your O is ;-). – No-Bugs Hare Jun 03 '15 at 11:56
  • 10^12 is already a lot though. You may have reasons to worry. – vib Jun 03 '15 at 11:57
  • 1
    Complexity is defined in terms of *operations* or *steps* of the program. There's no relation between a *step* and actual number of seconds a *step* (and in turn the whole program) may take to complete (to add up, BigO ignores *constants* and lower order *steps*). The actual execution depends on many factors such as CPU speed, number of CPU cores, nature of the program (e.g. IO intensive or CPU intensive). – P.P Jun 03 '15 at 11:58
  • You can get the runtime of algorithm with `O(n^x)` complexity using the formula: `c_x * n^x + c_x-1 * n^(x-1) ... + c_1 * n + c_0` where `c_x ... c_0` may be any value. They depend on the specifics of the algorithm, your cpu, scheduler state, and a lot of other things. – eerorika Jun 03 '15 at 11:58

4 Answers4

5

There is no way to calculate or estimate the running time of a some piece of code based on its Big-O rating.

Big-O tells you how a method scales in terms of operations to perform. It has no idea how long one operation take to execute. Additionally, CPUs may be good or bad at executing some of the operations in parallel which makes it even harder.

The only way to figure out if you have a performance bottleneck is to do the following:

  1. Observe the code running. Does it take too long?
  2. Measure the code running. Does it take too long?
  3. Narrow down the measurements until you know which part of the code is the main bottleneck.
  4. Decide if it can be changed, will you get out of it what you put into it?

If you also know the Big-O rating of that code you can use that to decide if the bottleneck is going to be exponentially worse if you, as an example, double the number of items to process.

Lasse V. Karlsen
  • 380,855
  • 102
  • 628
  • 825
2

You need to roughly know how much one of your base tasks takes in order to have an estimation of the running task for different Algorithms.

As an example, let's imagine your base task is

void func(){sleep(1)};

now you know that a O(1) complexity algorithm will yield to just one call to func(), which will take 1s.

Looking at other examples:

O(1) -> 1 * 1s
O(N) -> N * 1s
O(N2) -> (N^2) * 1s

Without having a rough estimation of your task's execution time, it is impossible to give a precise answer.

dau_sama
  • 4,247
  • 2
  • 23
  • 30
0

Easiest way to get the running time is to benchmark your algorithm with given n (run several times and use the mean). If the time is longer than what you have allocated for estimating the runtime, then you need to approximate.

You can get the exact runtime of algorithm with O(n^x) (polynomial) complexity using the formula: c_x * n^x + c_x-1 * n^(x-1) ... + c_1 * n + c_0 where the multipliers c_x ... c_0 may be any value. They depend on the specifics of the algorithm, your cpu, scheduler state, and a lot of other things.

You can estimate these multipliers by running your code with values of n small enough to not take more time that you have allocated for the estimation and creating statistics. You can use a polynomial regression model to estimate the multipliers. With the estimation, you can apply the multipliers to the above formula for approximation of the runtime with any value of n. The accuracy of the estimation depends on how much statistics you've gathered and how much larger n you're estimating for compared to the values of n used for the statistics and the order of the complexity (higher than quadratic may not be very useful).

The polynomial regression method itself is way beyond the scope of this question. I recommend reading a statistics text book for it. Here's a tutorial

Of course, you have to understand that these measurements and estimations only apply to your implementation of the algorithm running on your hardware and are not comparable to measurements of implementations of other algorithms or measurements on other hardware.

eerorika
  • 232,697
  • 12
  • 197
  • 326
-1

Big O is already pretty rough. Still, that means that you will execute something approximately 10^12 times, or a trillion iterations.

For example, an i7 4770K has 127,273 million instructions per second, at 3.9 GHz. This is a pretty meaningless metric generally, but since we are doing this very roughly, it will have to do.

At one instruction per iteration, it will apparently take around 8 seconds to complete.

In reality, you likely need a couple of instructions per iteration, but you also probably have less iterations (such as n/2). If you were to give us an example code, I could get a better guess.

mtijanic
  • 2,872
  • 11
  • 26