121 Week 12 - Operation Counting Flashcards
Experimental approach to finding runtime
Write a program to implement the algorithm then run it with varying input sizes and composition and record the running time.
Limitations of experimental approach
Need to implement the algorithm - time consuming.
Does not have results for all inputs.
Differences in hardware and software can cause inaccuracies.
Operation counting
A method of finding runtime of an algorithm by counting how many operations it executes.
Allows analysis of an algorithm independent of language used for implementation and execution.
What counts as an operation
An operation is a basic step or action that is performed in an algorithm, which takes constant time to execute, independent of the size of the input.
Differences between specific languages and compilers are ignored so that only the idea of the algorithm is analysed.
Finding T(n) based on input size
Count how many operations are executed for the algorithm.
If an operation is repeated e.g., in a for loop, multiply the number of operations in the loop by how many times they are executed. This could be a constant or have a variable e.g., executed 3n times where n is how many times the loop executes.
Worst, best and average case T(n)
Some algorithms do not always execute the same operations e.g., when if loops are included.
For this we find the best case (least operations are executed), worst case (most operations are executed) and average case (average number of operations executed) to be able to compare the algorithm.
Constant T(n)
Time taken for an algorithm to complete is independent of input size.
T(n) = A, where n is input size and A is a constant.
Linear T(n)
Time taken for an algorithm to complete is directly proportional to the size of the input ‘n’. Doubling/ halving n will approximately double/half the time taken to execute.
T(n) = An+B, where n is input size and A, B are constants.
Logarithmic function
Inverse of exponential functions.
b^c = a is equivalent to logb (a) = c where a > 0, b > 0, b != 1
Logarithmic T(n)
The time taken by this program is logarithmically proportional
to the size of the input.
T(n) = A*log n + B, where n is input size and A, B are constants.
Finding T(n) for a logarithmic algorithm
Find how many times each operation is executed for n=2^x.
Find the pattern for times executed of each operation in terms of x e.g., x+1.
Because n=2^x, log2(n) = x. This means we can replace all the x’s in times executed with log2(n).
You can now add up all the operations to find T(n) as all operations are expressed in terms of n.
Quadratic T(n)
Time taken is directly proportional to the square of the n.
T(n) = A*n^2 + Bn + C, where n is input size and A, B, C are constants.
Finding T(n) for a quadratic algoritm
Start by finding T(n) of the inner loop of the algorithm. Then find T(n) of the outer loop but substitute the operation count of the inner loop with T(n) of the inner loop.
