Big O

Question 1

Big O

Answer 1

In Computer Science, we use Big-O notation as a tool for describing the efficiency of algorithms with respect to the size of the input argument(s). n other words, how does our performance scale?

Question 2

O(1)

Answer 2

Constant complexity means that the algorithm takes roughly the same number of steps for any size input. In a constant time algorithm, there is no relationship between the size of the input and the number of steps required. For example, this means performing the algorithm on a input of size 1 takes the same number of steps as performing it on an input of size 128.

Question 3

O(log(n))

Answer 3

Logarithmic complexity algorithms will usual display a sense of continually “halving” the size of the input. Another tell of a logarithmic algorithm is that we don’t have to access every element of the input. O(log2(n)) means that every time we double the size of the input, we only require one additional step. Overall, this means that a large increase of input size will increase the number of steps required by a small amount.

Question 4

O(n)

Answer 4

Linear complexity algorithms will access each item of the input “once” (in the Big-O sense). Algorithms that iterate through the input without nested loops or recurse by reducing the size of the input by “one” each time are typically linear.

Question 5

O(n * log(n))

Answer 5

Loglinear - This class is a combination of both linear and logarithmic behavior, so features from both classes are evident. Algorithms the exhibit this behavior use both recursion and iteration. Typically, this means that the recursive calls will halve the input each time (logarithmic), but iterations are also performed on the input (linear).

Question 6

O(n^c)

Answer 6

Polynomial complexity refers to complexity of the form O(nc) where n is the size of the input and c is some fixed constant. For example, O(n3) is a larger/worse function than O(n2), but they belong to the same complexity class. Nested loops are usually the indicator of this complexity class.

Question 7

O(c^n)

Answer 7

Exponential complexity refers to Big-O functions of the form O(cn) where n is the size of the input and c is some fixed constant. For example, O(3n) is a larger/worse function than O(2n), but they both belong to the exponential complexity class. A common indicator of this complexity class is recursive code where there is a constant number of recursive calls in each stack frame. The c will be the number of recursive calls made in each stack frame. Algorithms with this complexity are considered quite slow.

Question 8

O(n!)

Answer 8

An indicator of this complexity class is recursive code that has a variable number of recursive calls in each stack frame. Note that factorial is worse than exponential because factorial algorithms have a variable amount of recursive calls in each stack frame, whereas exponential algorithms have a constant amount of recursive calls in each frame.

Question 9

Big O Analysis of Linear Search

Answer 9

O(n)

Question 10

Big-O Analysis of Binary Search

Answer 10

Time Complexity: O(log(n))
Space Complexity: O(n)
Use this algorithm when the input data is sorted!!!

Question 11

Big O Analysis of Merge Sort

Answer 11

Time Complexity: O(n log(n))

Space Complexity: O(n)

Question 12

Big-O Analysis of Bubble Sort

Answer 12

Time Complexity: O(n^2)

Space Complexity: O(1)

Question 13

Memoization

Answer 13

Memoization is a design pattern used to reduce the overall number of calculations that can occur in algorithms that use recursive strategies to solve.

Recall that recursion solves a large problem by dividing it into smaller sub-problems that are more manageable. Memoization will store the results of the sub-problems in some other data structure, meaning that you avoid duplicate calculations and only “solve” each subproblem once. There are two features that comprise memoization:

the function is recursive
the additional data structure used is typically an object (we refer to this as the memo!)

Question 14

Tabulation

Answer 14

Now that you are familiar with memoization, you can explore a related method of algorithmic optimization: Tabulation. There are two main features that comprise the Tabulation strategy:

the function is iterative and not recursive
the additional data structure used is typically an array, commonly referred to as the table

The Tabulation Formula
Here are the general guidelines for implementing the tabulation strategy. This is just a general recipe, so adjust for taste depending on your problem:

Create the table array based off of the size of the input, which isn’t always straightforward if you have multiple input values

Initialize some values in the table that “answer” the trivially small subproblem usually by initializing the first entry (or entries) of the table

Iterate through the array and fill in remaining entries, using previous entries in the table to perform the current calculation

Your final answer is (usually) the last entry in the table

Question 15

Big-O Analysis of Selection Sort

Answer 15

Time Complexity: O(n^2)

Space Complexity: O(1)

Question 16

Big-O Analysis of Insertion Sort

Answer 16

Time Complexity: O(n^2)
Space Complexity: O(1)

Insertion Sort has one advantage that makes it absolutely supreme in one special case. Insertion Sort is what’s known as an “online” algorithm. Online algorithms are great when you’re dealing with streaming data, because they can sort the data live as it is received.

If you must sort a set of data that is ever-incoming, for example, maybe you are sorting the most relevant posts in a social media feed so that those posts that are most likely to impact the site’s audience always appear at the top of the feed, an online algorithm like Insertion Sort is a great option.

Insertion Sort works well in this situation because the left side of the array is always sorted, and in the case of nearly sorted arrays, it can run in linear time. The absolute best case scenario for Insertion Sort is when there is only one unsorted element, and it is located all the way to the right of the array.

Well, if you have data constantly being pushed to the array, it will always be added to the right side. If you keep your algorithm constantly running, the left side will always be sorted. Now you have linear time sort.

Question 17

Big-O Analysis of Quick Sort

Answer 17

Time Complexity: O(n log(n))

Space Complexity: O(n)