Algorithm Analysis

To efficiently analyse a particular algorithm, we need to have some assumptions and rules to establish, and comply the #the rules stated.

Assumptions

Usually we will not count in the cost of the function and variable declaration, so it is fair to ignore them when dealing with algorithm efficiency. For input set, we will represent them as \(N\). For the rest of them, we will count them in one time unit.

Rules

There are several rules that we need to be aware.

First rule: The running time of a for loop is \(\le\) the running time of the statements inside the for loop \(\times\) the number of iterations.

Second rule: Apply the first rule, the total running time of a nested for loop is the running time of the statements \(\times\) the size of all the for loops.

Third rule: For consecutive statements, add them up and follow the #First Rule.

Forth rule: The running time of an if/else statement is \(\le\) the running time of the test + the largest of the running times of statement inside it.

Note: Most of the divide-and-conquer algorithms has a running time of \(O(\log N)\) since they use constant times to cut the input size by a fraction. However, if the input is not already there, then it will result in \(O(N \log N)\) which is slightly worse than \(O(N)\).

Note: Although usually lower order of algorithm speed is better than its higher order counterpart, this is not always the case. We need to take input size and development speed into accounts when determining whether it is good. If the performance improvement especially on small input size is negligible, it is better off with algorithm with lower order since most of the time it is easier to be developed and maintained.

Links to this page
  • Test Driven Development (TDD)

    The test data for these testing could be collected from real-world (usually user data coming from an existing system, a competitor’s system or a prototype) or artificially created (in order to satisfy the need of large amount of data, to stress the boundary conditions, or exhibits certain statistical properties such as the runtime of an algorithm#). These data can later be used in the Regression Testing#.

  • Square-and-Multiply Algorithm

    Square-and-Multiply Algorithm is an algorithm used to compute exponentiation, especially for larger numbers, by repeatedly squaring base and multiplying in the ones that are needed to compute the result looking at binary representation of the exponent. The running time# of it is \(O(\lg n)\).

  • Rivest-Shamir-Adleman (RSA)

    RSA is an #Asymmetric Cryptography scheme based on exponentiation in a Galois Field over integers modulo a prime which utilises integers as large as 1024 bits. The running time for exponentiation is \(o((\log n^3))\) operations, which is reasonable. However, to break the #algorithm, it needs \(o(e^{\log n \log \log n})\) factorisations, thus it is hard to crack#.

  • Comparison Sort

    Comparison Sort is a type of sorting algorithm that use simple comparisons such as larger than and lesser than. From 202201171853, while some of them would perform in \(O(N^2)\) in the worst case or even in average case, there are some could perform in \(O(N \log N)\) in the average case or even in the worst case.

#algorithm