\n
How to calculate Time Complexity for a given algorithm – The . My obvious answer to him was. There are tools available that do it for you!!” (E. Analyze menu in VS Team Suite, NDepend are a few). With that note, let me write a small program and calculate the time complexity for it. Here is a sample code to remove an invalid character from an array. That’s the key; you calculate the time complexity for each loop 1: for (int i = 0; i < N; i++) 2: . The basic operations it contains are int i=0; This will be executed only once. The time is actually calculated to i=0 and not the declaration. N; This will be executed N+1 timesi++ ; This will be executed N timesif(arr. Keep this mind; it is usually the same (unless you have a non- default FOR loop) Now for the second loop 1: for (int i = 0; i < ptr; i++) 2: . So, here it will take 2ptr+2 operations. Again, considering the worst case scenario ptr will be N so the above expression evaluates to (again) 2. N+2. Then there are these additional 2 operations of Console. Write with will be executed N times each (Again, worst case scenario). So the above code snippet will take . I almost forgot the other statementschar. This is because you are assigning one character at a time. So the rest of the code requires N+4 Adding everything up I get (N+4)+(5. N+2)+(4. N+2) = 1. N+8 So the asymptotic time complexity for the above code is O(N), which means that the above algorithm is a liner time complexity algorithm. There you have it, now you know how to calculate the time complexity of a simple program.
The Question How to find time complexity of an algorithm? Plz tell me how I would calculate time complexity of the program. Analysis of Algorithms.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. Archives
October 2017
Categories |