Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 calculating time complexity
Index -> General Programming
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
unoho




PostPosted: Tue Nov 23, 2010 7:11 pm   Post subject: calculating time complexity

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 Smile
Sponsor
Sponsor
Sponsor
sponsor
Brightguy




PostPosted: Wed Nov 24, 2010 1:40 am   Post subject: Re: calculating time complexity

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




PostPosted: Thu Nov 25, 2010 12:51 am   Post subject: RE:calculating time complexity

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.
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
A.J




PostPosted: Thu Nov 25, 2010 12:57 am   Post subject: RE:calculating time complexity

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
Display posts from previous:   
   Index -> General Programming
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 4 Posts ]
Jump to:   


Style:  
Search: