Alex Rivera | Logout

Can a program calculate the complexity of an algorithm?

Asked 2012-01-11T00:55:30.097
10

Is there any way to compute the time complexity of an algorithm programatically? For example, how could I calculate the complexity of a fibonacci(n) function?

Edit
Report

1 Answer

1

Not in general. If the algorithm consists of nested simple for loops, e.g.

for (int i=a; i<b; ++i)

then you know this will contribute (b-a) steps. Now, if either b or a or both depends on n, then you can get a complexity from that. However, if you have something more exotic, like

for (int i=a; i<b; i=whackyFunction(i)) 

then you really need to understand what whackyFunction(i) does.

Similarly, break statements may screw this up, and while statements may be a lost cause since it's possible you wouldn't even be able to tell if the loop terminated.

answered 2012-01-11T01:06:17.813

Your Answer