Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to find computational complexity?

  1. Sep 4, 2007 #1
    If i have a program, how can i find the computational complexity? is there some other program i can run in the background?
  2. jcsd
  3. Sep 4, 2007 #2


    User Avatar
    Science Advisor
    Homework Helper

    A first step would be counting the nested loops and looking at the number of times they execute. If you have three nested loops, each running from 1 to x, and inside the three you have operations taking constant time (i.e. not dependent on the size of any variable) then the complexity is [itex]\mathcal{O}(n^3)[/itex].

    If you're using bignums or the like you'll have to look into how much each operation costs based on the size of the numbers -- that's usually log(x)^k log(log(x))^n for some k and n. If you have a loop from 1 to x doing schoolbook multiplication on a bignum of size x, that's complexity [itex]\mathcal{O}(x(\log x)^2)[/itex].
    Last edited: Sep 4, 2007
  4. Sep 4, 2007 #3
    thanks for your help. can u point me to some resource where i can look some of this stuff up?
  5. Sep 5, 2007 #4


    User Avatar

    If you're using standard library functions, most programming language standards will specify the mandatory asymptotic running time in the standard. If you're wanting to analyse your own code, then a good book (the standard in universities, pretty much), is Introduction to Algorithms by CLRS.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook