Guidelines for Asymptotic Analysis
There are some rules to help us determine the running time of an algorithm. I have described with an example using python code
- Loops: The running time of a loop is, at most, the running time of the statements inside the loop (including tests) multiplied by the number of iterations.
2. Nested loops: Analyze from the inside out. Total running time is the product of the sizes of all the loops.
3. Consecutive statements: Add the time complexities of each statement.
4. If-then-else statements: Worst-case running time: the test, plus either the then part `the else part (whichever is the larger).
5. Logarithmic complexity: An algorithm is O(logn) if it takes a constant time to cut the problem size by a fraction (usually by 1/2 ). As an example let us consider the following program:
If we observe carefully, the value of i is doubling every time. Initially i = 1, in next step i = 2, and in
subsequent steps i=4,8 and so on. Let us assume: that the loop is executing some k times. At kth step 2^k = n
and we come out of the loop. Taking logarithm on both sides gives.
Another example: binary search (finding a word in a dictionary of n pages)
• Look at the center point in the dictionary
• Is the word towards the left or right of the corner?
• Repeat the process with the left or right part of the dictionary until the word is found.
