In the sub-module on algorithms, we saw that in order to specify an algorithm, we needed
- An assignment operator to assign a value to a variables and create an assignment statement (e.g., = in Java or C++);
- A series of operators to compare values (e.g, ==, <, >) and thus create tests;
- Some logical operators to combine tests into more complex tests (e.g., && and || in Java and C++);
- A conditional to branch depending on the outcome of a test (if-then-else);
- A way to make a sequence of statements;
- A way to repeat statements, for which we used iteration (e.g., for-loops).
We can use these constructs to determine the time-complexity of an algorithm by using the following rules:
- The complexity of an assignment, a test and a combination of test is constant, i.e. it is O(1).
- The complexity of an if-then-else statement is the maximum of the complexity of the then-part and the else-part. Thus,
O (if <some_test> { <then-part> } else { <else-part> } ) =
MAX(O(<then-part>), O(<else-part>))
- The complexity of a sequence of statement is the maximum of the complexity of the statements in the sequence. Thus,
O (<statement-1>; <statement-2>; .... ; <statement-n>;) =
MAX(O(<statement-1>), O(<statement-2>), ... , O(<statement-n>))
- The complexity of a for loop is the complexity of the body of the loop times the number of times we go throught the loop. Thus,
O (for(i = 0; i < n; i++){<body>}) = n * O(<body>)
Watich the videos "Time complexity analysis - How to calculate running time?" and "Time complexity analysis - some general rules" at http://www.youtube.com/playlist?list=PL2_aWCzGMAwI9HK8YPVBjElbLbI3ufctn for more details and some examples. As before, you will have to watch some adverts. Also, the video "Time complexity analysis - some general rules" mentions asymptotic notations and in particular theta. You can understand the material without knowing additional details about these concepts, but if you are interested watch the video "Time complexity analysis: asymptotic notations - big oh, theta ,omega" at the same site.