calculating time complexity

[unoho]

just wondering if anyone got any good tutorials on how to calculate time complexity. right now, we are doing that in class and i really don't understand how the prof finds the time complexity (let's say O(n^2)) just by looking at the code. like i know for small codes (like bubble sort etc) it's easy to find it but if you never saw the code before, how would you find it's time complexity just by looking at it?

any tips/tutorial/advice is always appreciated

[Brightguy]

I think you may have to be more detailed about how you need help.

Generally a problem like this is to express, in the worst-case, the number of operations an algorithm will use in terms of the size of its input. The units of "operations" and "size" depend on the problem; for example "operations" may count the number of additions or multiplications or comparisons of integers of some size, and "size" may count the number of integers of some size. Often the input size is denoted n, and the answer is expressed using big oh notation.

So, for example, for a straightforward way to compute the time complexity of a loop, you could figure out the maximum number of times the loop could possibly run (on input size n), and the maximum number of operations that could possibly occur during any iteration. Then the loop complexity is O(total_loops*iteration_operations); note although this may not be the most precise answer, it is still correct.

To compute the complexity of a recursive algorithm you generally have to have to express the answer in the form a recurrence, which you can then hopefully solve for a closed-form answer.

[Tony]

The way you are familiar enough with Bubble Sort to "just see" its complexity, your prof is familiar with a greater variety of code examples. There are certain patterns to look for, but those essentially just give you a gut-feeling estimate. For assignments you would typically have to mathematically prove/calculate the complexity, which is a fairly different exercise than just getting a feel for the answer... But one skill helps with the other, and from then on it's just practice.

[A.J]

Take a look at the following link to help you understand time complexity a bit more: http://www.student.cs.uwaterloo.ca/~cs145/handouts/order-notation.pdf