Search code examples
algorithmbig-otime-complexity

Rough estimate of running time from Big O

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

Solution

  • 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.