By Ira Herman
Live Video Walkthrough (bonus lesson) recording
================
Big O Notation:
- Time/Space Complexity review: Big O Notation
Data Structures:
- Arrays - how they work with memory/addressing
- Hash Maps/Hash Tables
- Linked Lists (Singly and Doubly)
- Stacks LIFO and Queues FIFO
- Trees
- Graphs
Algorithms:
- Recursion
- Sorting - Bubble Sort
- Searching - Binary Search
================
Key words: analyzing the "complexity" of an algorithm. We'll look at time complexity (how long it takes to do something), but this can also be applied to space complexity - how much space/memory it will take up.
Big O analysis is a way to measure the time it takes (speed/efficiency) of an algorithm regardless of processor or hardware speed. So it is timeless -- even as computers get faster and faster, we can apply the same Big O analysis to an algorithm.
- Is the amount of work the same, regardless of the size of the data set?
- You might have O(1).
- Does the function have to go through an entire list (use a loop)?
- If so, there’s an N in that Big O class somewhere.
- Are there nested loops?
- That might give you O(N^2) (or worse).
- Does the function break the list into smaller chunks?
- You could have O(log(N)).
- Constant complexity: O(1).
- Linear complexity: O(N).
- Quadratic complexity: O(N^2).
- Logarithmic complexity: O(log(N)).
- Factorial complexity: O(N!).
The main ones you'll usually be asked about are the first 4:
- O(1)
- O(N)
- O(N^2)
- O(log(N))
A good example: Binary search.
The traveling salesman problem.
More details here
Take a look at the code samples here and analyze the time complexity using Big O notation:
Ira's Big O Code Samples repl.it
const groceries = ["eggs", "bread", "cheese", "milk", "chocolate"];
const stores = ["Whole Foods", "Sprouts", "Ralphs", "Safeway"];
////////////////////////////////////////////////////
// 1:
// What is the time complexity of this algorithm?
function getGrocery(arr, index){
return arr[index];
}
getGrocery(groceries, 4);
////////////////////////////////////////////////////
// 2:
// What is the time complexity of this algorithm?
function listGroceries(arr){
for (let i=0; i < arr.length; i++){
console.log(arr[i]);
}
}
listGroceries(groceries);
////////////////////////////////////////////////////
// 3:
// What is the time complexity of this algorithm?
function listGroceriesAtEachStore(storesArr, groceriesArr){
for (let i=0; i < storesArr.length; i++){
console.log(storesArr[i]);
for (let j=0; j < groceriesArr.length; j++){
console.log(groceriesArr[j]);
}
}
}
listGroceriesAtEachStore(stores, groceries);
The code: Linked list example implementation repl.it
// Singly Linked List:
class LinkedList {
constructor(value) {
this.head = {
value: value,
next: null
};
this.tail = this.head;
this.length = 1;
}
append(value) {
const newNode = {
value: value,
next: null
}
this.tail.next = newNode;
this.tail = newNode;
this.length++;
return this;
}
prepend(value) {
const newNode = {
value: value,
next: null
}
newNode.next = this.head;
this.head = newNode;
this.length++;
return this;
}
printList() {
const array = [];
let currentNode = this.head;
while(currentNode !== null){
array.push(currentNode.value)
currentNode = currentNode.next
}
return array;
}
insert(index, value){
//Check for proper parameters;
if(index >= this.length) {
console.log('yes')
return this.append(value);
}
const newNode = {
value: value,
next: null
}
const leader = this.traverseToIndex(index-1);
const holdingPointer = leader.next;
leader.next = newNode;
newNode.next = holdingPointer;
this.length++;
return this.printList();
}
traverseToIndex(index) {
//Check parameters
let counter = 0;
let currentNode = this.head;
while(counter !== index){
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
remove(index) {
// Check Parameters
const leader = this.traverseToIndex(index-1);
const unwantedNode = leader.next;
leader.next = unwantedNode.next;
this.length--;
return this.printList();
}
}
let myLinkedList = new LinkedList(10);
myLinkedList.append(5);
myLinkedList.append(16);myLinkedList.prepend(1);
myLinkedList.insert(2, 99);
myLinkedList.insert(20, 88);
myLinkedList.remove(2);The code: Doubly Linked list example implementation repl.it
class DoublyLinkedList {
constructor(value) {
this.head = {
value: value,
next: null,
prev: null
};
this.tail = this.head;
this.length = 1;
}
append(value) {
const newNode = {
value: value,
next: null,
prev: null
}
console.log(newNode)
newNode.prev = this.tail
this.tail.next = newNode;
this.tail = newNode;
this.length++;
return this;
}
prepend(value) {
const newNode = {
value: value,
next: null,
prev: null
}
newNode.next = this.head;
this.head.prev = newNode
this.head = newNode;
this.length++;
return this;
}
printList() {
const array = [];
let currentNode = this.head;
while(currentNode !== null){
array.push(currentNode.value)
currentNode = currentNode.next
}
return array;
}
insert(index, value){
//Check for proper parameters;
if(index >= this.length) {
return this.append(value);
}
const newNode = {
value: value,
next: null,
prev: null
}
const leader = this.traverseToIndex(index-1);
const follower = leader.next;
leader.next = newNode;
newNode.prev = leader;
newNode.next = follower;
follower.prev = newNode;
this.length++;
console.log(this)
return this.printList();
}
traverseToIndex(index) {
//Check parameters
let counter = 0;
let currentNode = this.head;
while(counter !== index){
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
}
let myLinkedList = new DoublyLinkedList(10);
myLinkedList.append(5)
myLinkedList.append(16)
myLinkedList.prepend(1)
myLinkedList.insert(2, 99)
// myLinkedList.insert(20, 88)
// myLinkedList.printList()
// myLinkedList.remove(2)
// myLinkedList.reverse()The code: Fibonacci loop and recursive solution implementations repl.it
// Given a number N return the index value of the Fibonacci sequence, where the sequence is:
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...
// the pattern of the sequence is that each value is the sum of the 2 previous values, that means that for N=5 → 2+3
//For example: fibonacciRecursive(6) should return 8
function fibonacciIterative(n){
let arr = [0, 1];
for (let i = 2; i < n + 1; i++){
arr.push(arr[i - 2] + arr[i -1]);
}
return arr[n];
}
fibonacciIterative(3);
function fibonacciRecursive(n) {
if (n < 2){
return n;
}
return fibonacciRecursive(n - 1) + fibonacciRecursive (n - 2)
}
fibonacciRecursive(6)The code: Factorial loop and recursive solution implementations repl.it
function findFactorialIterative(number) {
let answer = 1;
// you actually no longer need the if statement because of the for loop
// if (number === 2) {
// answer = 2;
// }
for (let i = 2; i <= number; i++) {
answer = answer * i;
}
return answer;
}
function findFactorialRecursive(number) {
if(number === 2) {
return 2;
}
return number * findFactorialRecursive(number - 1)
}
findFactorialIterative(5);
findFactorialRecursive(5);
//If you want, try to add a base case condition for the recursive solution if the parameter given is less than 2