Search code examples
performancetestingtimerruntime

Does the more time a function takes means its runtime complexity is larger?

Is it wise to verify runtime complexity of code with timer tests?

For example:

x=very large input

timer start
foo(x)
timer end

print time

So if the time was 0 seconds then that means foo runs on O(n) or less and if timer is say 30-60 seconds, that means the runtime has to be larger than O(n)?

In general, does more time a function takes then that means it's runtime complexity is larger?

Solution

  • Runtime complexity or Asymptotic complexity is part of apriori analysis. To put it simply, these are theoretical measures of code.

    For example,

    function foo (){
    for (i=1;i++;i<n)
        do x;
}

    According to above example,

    Apriori (before running the code) analysis says, its runtime complexity will be O(n), as the loop will get executed n-1 times.

    Suppose if we run this code, we found out that code is taking 1 min to execute. Then we can conclude below things,

    1. the do() function is taking more time -- it is costly
    2. Running complexity is O(n)

    The conclusion in running complexity is based on data structures and loops. They are not related to actual running time.

    It doesn't matter if your code is taking 1 sec or 1 hr to execute, runtime complexity is fixed for a piece of code. Time is getting wasted somewhere in that function.

    It is simple if you write a simple program for printing 1-n in a loop.

    For us time complexity is always O(n) as long you are printing 1-n. but if your print command takes 3 sec to print a number, then your program is taking high time to execute, but it doesn't mean time complexity is O(n^2).