CP164 Study Guide - Final Guide: Analysis Of Algorithms
Big-O Notation
Rules of Thumb for Determining Big-O
When new to algorithm analysis, determining the time complexity of an algorithm can
seem daunting and difficult. There are, however a few rules of thumb to go by to give you a
rough idea of what an algorithm's time complexity is likely to be:
• If the algorithm has no loops or recursive calls, then the algorithm is O(1), or
of constant time complexity. The size of the data does not matter - without a loop or
recursive call, the algorithm can't take more time.
• If the algorithm has a single loop (or equivalent recursion), examine the amount of data left
to be processed after one iteration. If the amount left is n-1the algorithm is O(n), or
of linear complexity.
• If the algorithm has a single loop (or equivalent recursion), and after the first iteration the
amount of data left to process is n/2 (or n/k - the divisor doesn't matter), the algorithm
is O(log n), or of logarithmic complexity.
• If the algorithm has nested loops (or the recursive equivalent), then examine the loops
separately as above. If both loops are linear, then the algorithm
is O(n2) (or quadratic complexity). If one is linear and the other is logarithmic, then the
algorithm is O(n log n) complexity.
What if an algorithm contains independent sets of loops rather than nested? For example, a
loop of linear complexity (O(n)) followed by a loop of logarithmic complexity (O(log n))?
The highest order of the independent loops determines the overall order. Thus the above
example is O(n), because that is the dominant complexity.
The algorithms in order of complexity are:
O(1) < O(log n) < O(n) < O(n log n) < O(n2)
Other complexities are certainly
possible: O(2n) (exponential), O(n3) (cubic), O(n!) (factorial). However, we hope not to run
into these complexities in this course.
Choosing an Algorithm
How should you choose an algorithm? Is the algorithm with the lower complexity always
better than the algorithm with the higher complexity? This depends on the size of n.
Examine the following actual running times given by the formulae below:
• f1(n) = 50,000 log2n + 5
• f2(n) = 400n + 20
• f3(n) = 3(2n) + 6n2 + 0.2
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
When new to algorithm analysis, determining the time complexity of an algorithm can seem daunting and difficult. There are, however a few rules of thumb to go by to give you a rough idea of what an algorithm"s time complexity is likely to be: If the algorithm has no loops or recursive calls, then the algorithm is o(1), or of constant time complexity. The size of the data does not matter - without a loop or recursive call, the algorithm can"t take more time. If the algorithm has a single loop (or equivalent recursion), examine the amount of data left to be processed after one iteration. If the amount left is n-1the algorithm is o(n), or of linear complexity. If the algorithm has nested loops (or the recursive equivalent), then examine the loops separately as above. If both loops are linear, then the algorithm is o(n2) (or quadratic complexity).
