02 Prove : Homework - Data Structures
Big-O Analysis
Outcomes
At the end of this study, successful students will be able to:
Articulate the value of Big-O Analysis.
Perform Big-O Analysis in simple situations.
Overview
This semester we will be comparing many different data structures. In so doing, we may want to say "mine is better than yours" in one situation or another, but in order to do that we need to be able to explain or prove that it's true for certain conditions.
This is where Big-O notation comes into play. It is the language and process we use to be able to rigorous define when something truly is faster or smaller than something else.
Preparation Material
First, please read the following
As stated in the above reading, the purpose of Big-O analysis is for us to be able to analyze algorithms in a way that isn't influenced by how fast a certain computer is, or what language it is written in. Instead, we focus on the fundamental pieces of the algorithm itself.
As a rule of thumb, here are some common cases that map to a Big-O class. These are ordered from lowest to highest, and there are big differences between each of these categories.
-
O(1) - "Constant Time" - This means that the algorithm does not depend on the size of the problems.
For example, the effort it takes to print the first number of a list does not depend on how many items are in the list.
-
O( log(n) ) - "Logarithmic Time" - This is usually the case when we find a problem that we can cut in half (or some other amount), each time we take a step.
For example, if you had a sorted list of 1,000 different numbers, and you were trying to find a certain one. You could start by checking in the middle. If that number is less than your desired one, you could rule out all the numbers in the first half of the list, and focus exclusively on the second half. Then, you could look at the number in the middle of that half, and rule out all of them to one side or the other of that one. Each time you do this, you are reducing the problem to half the size of the previous one.
Logarithmic time is considered to be very good in most cases.
-
O(n) - "Linear Time" - In this case, the number of steps of the algorithm grows proportionally to the size of the problem.
For example, if you wanted to find a particular number in a list that was not sorted, you have no other choice but to start at the beginning of the list and work your way through it. If there are 100 numbers, in the worst case, you have to look at all 100. If there are 1,000, you might have to look at all 1,000.
This is usually the complexity if you have a single for loop that iterates over a list.
-
O( n * log(n) ) - This is worse than O(n) but better than O(n^2). We will see it come up a lot in our study of sorting algorithms.
-
O(n^2) - In this case, the steps needed to solve the problem grow at a rate much faster than the size of the problem itself.
For example, if you wanted to see if an unsorted list contained duplicate values. You might consider starting with the first one, then comparing it against everything else in the list. Then, consider the second value and compare it against everything else in the list.
As in this example, most O(n^2) problems tend to have a loop within a loop. (Notice this is very different than having two loops one right after another, which would only be O(n). It is the fact that the second loop is nested inside the first that makes it so much worse.)
-
O(n^3) - Even worse than O(n^2), some problems might require 3 loops inside of each other.
-
O(2^n) - "Exponential" problems are considered very expensive. Often these are the kinds of algorithms/problems that would be used in security or encryption because they are very difficult to use a "brute force" solution on. With something as small as n=100, an exponential problem requires O(2^100) or approximately O(10^30) steps. Yikes!
-
O(n!) - "Factorial" problems are extremely large and would be very difficult to run an algorithm on a size bigger than something trivial. For reference, 100! is approximately 10^157.
Submission
When you have a good understanding of this topic, take the accompanying I-Learn Quiz.
Please note that this quiz will allow you to take it multiple times, so that you can make sure that by the end, you know the answers to all the questions. Future data structures quizzes will not allow multiple submissions.