# How to find computational complexity?

1. Sep 4, 2007

### Coolphreak

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

2. Sep 4, 2007

### 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)$.

Last edited: Sep 4, 2007
3. Sep 4, 2007

### Coolphreak

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

4. Sep 5, 2007

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