0

Is there a math formula that I can put in my Windows calculator to calculate the time cost of my nested loop?

From what I read, I saw things like O(n) but I don't know how to put that in a calculator.

I have a 300 levels nested loop, each loop level will go from 0 to 1000

So it is like:

for i as integer =0 to 1000
{
 //300 more nested loops, each goes from 0 to 1000
}

I am assuming that 1 complete loop will take 1 second (i.e. the 300 levels from the top most loop to the inner most loop will take 1 second).

How can I find out how many seconds it will take to complete the whole loop operation?

Thank you

Ibrahim D.
  • 318
  • 4
  • 17
  • 1
    If you nest 301 loops, each with 1001 steps, the inner-most code will run 1.3510061352833213568150396557293666843498038319887390... × 10^903 times. The universe will come to an end before you have done any noticeable progress. (Essentially, you will be at 0.000000000000000... % completion when the universe has come to its end.) – Andreas Rejbrand Dec 18 '17 at 07:16
  • @AndreasRejbrand hahaha, actually this what I am trying to figure out..will my nested loop be completed in the universe's lifetime or not. But it will end at some point for sure. Can you point me to an equation I can use to tell me exactly how many seconds it will take? I am using big data calculator, so I think it can handle large numbers – Ibrahim D. Dec 18 '17 at 07:44
  • 1
    The number of times the code will be run is 1001^301. If the code takes *t* seconds to complete, the total running time will be no less than 1001^301 *t* seconds. – Andreas Rejbrand Dec 18 '17 at 07:50
  • @AndreasRejbrand Great!, thank you...you should post it as answer so I can accept it :) – Ibrahim D. Dec 18 '17 at 08:00

1 Answers1

2

If you have M nested loops each with N steps, the total number of times the inner-most code will run is NM. Consequently, if this code takes t seconds to execute, the total running time will be no less than NMt.

In your case, N = 1001 and M = 301. Thus

NM = 1351006135283321356815039655729366684349803831988739053240801914465955329955010318785683390381893021480038259097571556568393033624125663039020474816807139123124687688667110651554536455554983313531622053666601142890485454586020409971220427023079449603217442510854172465669657551198374621035716253537483681789962979899381794117593366167602159102878741666110186140811771157661856975727227011774938173689257851684515033630838203428990519981303994460521486651131205651440789014004132287034501678194895276766533222238644463714676717122486815519675003623218747516074833762258750872602504763945523812443905022112877989765178585281722001229086777672022301235387486256207147702409003911671750616133700186863997717468027217550738860605995255072363983914048955786591110292838269781981812167453230775137941595147968127169264749956845265384891251656562329411331097495063637387550896404766837508698223985774995150301001.

If, in addition, we assume that the inner-most code is really fast, like t = 1 µs, the total running time will be no less than NMt = 1.35... × 10897 s.

When the universe comes to its end, your code will be at almost exactly 0.0000000000000000000000000000 % completion, assuming the hardware hasn't faulted by then and the human civilization hasn't come to an end (thus making it difficult for you to find the electrical power you need to run your hardware).

Andreas Rejbrand
  • 105,602
  • 8
  • 282
  • 384
  • Hahahaha lets hope it doesn't end before I get to finish the loop – Ibrahim D. Dec 18 '17 at 08:22
  • @IbrahimD.: Indeed. In practice, you should never nest more than two or three loops. If N^M gets larger than about 10000000000, there is no hope. – Andreas Rejbrand Dec 18 '17 at 08:31
  • @AndreasRejbrand I've had loops complete with N^M [ten thousand times larger](https://stackoverflow.com/q/3499798/341362). But at that point you're talking about highly specialized code and either lots of cores or many months of computation. – Charles Dec 18 '17 at 20:35