Big O Notation, Part 2

Big-O, Part 2

Homework the night before:

In preparation for the Big O Notation (Part 2) class, please review the following Big O Notation class from Mod 3: https://vimeo.com/441951062/1516a80c38

Introduction

We’re going to be reviewing some of the Big O Notation lesson from Mod 3, and examining some additional terminology and working through some additional interview challenges to practice high-level design and Big O Analysis.

Big O Notation is one of those topics where you’ll stand out from other candidates applying for a job, especially if you can VOLUNTEER Big O Notation terminology during an interview without being prompted.


Vocab / Review (30 minutes)

  • Algorithm A set of rules and processes for solving a problem
  • Big-O Notation A description of the worst-case performance of an algorithm

What is Big-O?

Big O notation is used in Computer Science to describe the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.

You can think about these as ratings for your algorithm. These ratings can communicate the amount of space and time you can expect your algorithm to need.

A good analogy is “horsepower”, a term coined by James Watt in Scotland in the 1800’s to teach a comparison of power between draft horses and steam engines (and later other types of engines and machines). In today’s society, while we may not understand the intricacies of how an automobile works, we generally know that a 200-horsepower engine is better than a 100-horsepower engine.

Likewise, with Big O Notation, we can get a sense of EFFICIENCY of an algorithm, instead of the POWER of an engine as in the previous example. With Big O, however, less complexity is better than more efficiency.

Factors in determining complexity

  • Number of comparisons or operations
  • Amount of space used in memory

The number of elements in a data structure are counted, and generally use “n” as an algebraic replacement for the actual number. So if we have 100 elements in an array or 1,000,000, we substitute “n” for the count of those elements when determining how much work our algorithm is doing.

Big-O Cheatsheet Review

Big-O Complexity

Quick Analysis of Why Big O matters:

      | O( log n )    | O( n ) |    O( n^2 )   | O( 2^n )
------------------------------------------------------------
100   |     2	      |    100 |        10,000 | 1.27E+30
------------------------------------------------------------
1000  |     3	      |  1,000 |     1,000,000 | 1.07E+301
------------------------------------------------------------
10000 |     4	      | 10,000 |      1.00E+08 | 1.07E+3010
------------------------------------------------------------

More Terminology Review:

Review the name of each of the following Big O Notation equations, and one example of use within an algorithm:

  • O(1)
  • O(n)
  • O(log n)
  • O(n log n)
  • O(n^2) (aka, n-squared)

Reviewing Space Complexity and Big O Analysis

Space … The Final Frontier

When we discuss Big O Complexity, we sometimes talk about “space complexity” as well. Recall in Mod 3 that we did not include individual variables in how much RAM we use, nor do we count “transient” data structures like array slices generated by our language of choice. We ONLY count data structures that we make ON PURPOSE in order to track/sort/calculate/store data for some kind of outcome.

We generally use a “modifier” notation, like “1X” or “2X”, where “1X” represent that we did not use any more memory than the data structure provided to us. “2X” would indicate that we’ve added a second data strcuture of some kind. Which data structure, and what it holds, is less relevant.

Analysis

  • Assume the worst-case scenario
  • Remove constants (O(3n) is fundamentally the same as O(n))
  • Use different terms for inputs ONLY if the inputs are dramatically different in size

New Terminology

O(n * m) - This doesn’t have a good name (yet)

When we talk about quantities of numbers in a data set, we use “n” to describe the count. But what if we need to do an operation on one data set which is extremely large, against another data set which is extremely small? Should we use “n” in both cases?

Let’s use “n” for our largest set, and “m” for our smallest set, and compare using the following prompt:

A list of teachers is responsible for grading a number of students. Generate a list of students for each teacher.

set teacher_list = ['Alex', 'Eric', 'Megan', 'Casey']
set student_list = ['Able', 'Becca', 'Carlos', 'Demarcus', 'Edwin', 'Francesca', 'Gary', ...]

set teacher_index to 0
set last_teacher_index to -1

for each "student" in student_list:
  if teacher_index is not equal to last_teacher_index:
    print "---\n list of students for " + teacher_list[teacher_index]
    set last_teacher_index = teacher_index
    set teacher_index = teacher_index + 1
  print student

If the number of teachers is 10, and the number of students is 100, those sizes aren’t too different. In this case, we could say the algorithm is O(n^2).

However, let’s say there are only 10 teachers for 10,000 students. Now the numbers are significantly different, by several “orders of magnitude”. In this case, we would use “m” to represent our smaller data set, the teachers, and classify this algorithm as O(n * m) – which is more than Linear Time (O(n)), but less than Quadradic Time (O(n^2))

O(2^n) - Exponential Time

For each new item, “n”, the growth of work doubles.

The most common algorithm for this is the Fibonacci Sequence, where the next number in the sequence is the sum of the preceding two numbers. This list always starts with [0, 1] and grows to look like [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …]

This algorithm is typically built using recursion where we want to find the “N-th” number in the sequence. For example, what is the 30th number in the Fibonacci sequence? (the answer is 832,040)

function fibonacci(nth_number):
  if n is less than 0:
    print "ruh-roh, invalid input"
  else if n === 0:
    return 0
  else if n === 1:
    return 1
  else:
    return fibonacci(nth_number - 1) + fibonacci(nth_number - 2)

In this sequence, each new “N-th” number we want to find needs TWO function calls to the fibonacci() method to calculate the answer.

More Exercises

Your instructors will provide one or more additional technical challenges for you and a small group of others. Work together to determine a high-level design for solving the problem (no actual code!), and then analyze the Big O Notation of your solution.

Resources

Lesson Search Results

Showing top 10 results