How to find computational complexity?

[Coolphreak]

If i have a program, how can i find the computational complexity? is there some other program i can run in the background?

 

[CRGreathouse]

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 \mathcal{O}(n^3).

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 \mathcal{O}(x(\log x)^2).

 

[Coolphreak]

thanks for your help. can u point me to some resource where i can look some of this stuff up?

 

[dpm]

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.