What is the difference? ... Well, the main thing is that as an automated tester, I haven't needed to worry about Big-O notation and sorting algorithms, such as the ones found on Eric Drowell's Big-O Cheat Sheet.
In this blog post, we are going to be focusing on walking through the sorting algorithms Insertion Sort, Mergesort, and Quicksort, and implementing them in Java code.
Big O notation is how computer scientists compare and contrast the efficiency of sorting and searching algorithms, the tried-and-true recipes used to write programs that search through massive amounts of data.
The concept of Big O notation was first introduced and the popularized by the German mathematicians, first by Paul Gustav Bachman, in his book on analytical number theory, Analytische Zahlentheorie, and then by Edmund Landau.
The "O" symbol mentioned in the book was initially an omicron, the 15th letter of the Greek alphabet, showing a formula to show the formula of a rate of growth.
"Big O notation (with a capital letter O, not a zero), also called Landau's symbol, is a symbolism used in complexity theory, computer science, and mathematics to describe the asymptotic behavior of functions. Basically, it tells you how fast a function grows or declines.
"For example, when analyzing some algorithm, one might find that the time (or the number of steps) it takes to complete a problem of size n is given by T(n) = 4 n2 - 2 n + 2.
"If we ignore constants (which makes sense because those depend on the particular hardware the program is run on) and slower growing terms, we could say 'T(n) grows at the order of n2' and write: T(n) = O(n2). - MIT 16.070, Introduction to Computers and Programming.
Here is a list of functions, from slow growing to fast growing. If you are dealing with massive amounts of data, you want to match the most effective searching or sorting algorithm with its Big O notation.
What Was That About Complexity?
"O(1)/Constant Complexity: Constant. This means irrelevant of the size of the data set the algorithm will always take a constant time. 1 item takes 1 second, 10 items takes 1 second, 100 items takes 1 second. It always takes the same amount of time.
"O(log n)/Logarithmic Complexity: Not as good as constant, but still pretty good. The time taken increases with the size of the data set, but not proportionately so. This means the algorithm takes longer per item on smaller datasets relative to larger ones. 1 item takes 1 second, 10 items takes 2 seconds, 100 items takes 3 seconds. If your dataset has 10 items, each item causes 0.2 seconds latency. If your dataset has 100, it only takes 0.03 seconds extra per item. This makes log n algorithms very scalable.
"O(n)/Linear Complexity: The larger the data set, the time taken grows proportionately. 1 item takes 1 second, 10 items takes 10 seconds, 100 items takes 100 seconds.
"O(n log n): A nice combination of the previous two. Normally there’s 2 parts to the sort, the first loop is O(n), the second is O(log n), combining to form O(n log n) 1 item takes 2 seconds, 10 items takes 12 seconds, 100 items takes 103 seconds.
"O(n^2)/Quadratic Complexity: Things are getting extra slow. 1 item takes 1 second, 10 items takes 100, 100 items takes 10000.
"O(2^n): Exponential Growth! The algorithm takes twice as long for every new element added. 1 item takes 1 second, 10 items takes 1024 seconds, 100 items takes 1267650600228229401496703205376 seconds.
"It is important to notice that the above is not ordered by the best to worst complexity. There is no 'best' algorithm, as it completely hinges on the size of the dataset and the task at hand".
If you are more of a visual person (like me), maybe this chart would help. It is taken from Richard Meyr's lecture on Discrete Mathematics.
If you really want to know what Logarithmic functions are about, I would suggest the free class at Khan Academy, as part of its Algebra II course, Introduction to Logarithms.
With exponents, 24 (or 2 ^ 4, two to the power of four) is 2 * 2 * 2 * 2 ==> 16.
What if we want to find out, though, the power that 2 needs to be raised by to get the answer of 16?
... We just found that out... x = 4.
We can write it as: log216 = x.
And log3 81 = x is the same as 3x = 81 ... which is 3 * 3 * 3 * 3 => x = 4. Or "The log of base 3 of 81 is 4".
Let's say you wanted to use a Binary Search Algorithm to search through a list of numbers, and you have read that it has a Big O of log n when it comes to searching through the numbers. How many tries, worse case scenario, would it take to search through eight numbers? Sixteen? Thirty-two? Sixty-four? A thousand? A million?
... It's okay if you don't know what binary search algorithms are. We will go into that later.
If there are eight numbers, it will take a maximum of three tries to get the number.
If there are sixteen numbers, it will take a maximum of four tries to get the number.
If there are thirty-two numbers, it will take a maximum of five tries to get the number.
If there are a thousand numbers, it will take a maximum of ten tries to get the number.
If there are a million numbers, it will take a maximum of twenty tries to get the number.
... So, that's how you use Logarithms to calculate the efficiency of your algorithm!