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.