• Motivate the need for sth like Big O Notation
• Describe what Big O Notation is
• Simplify Big O Expressions
• Define "time complexity" and "space complexity"
• Evaluate the time complexity and space complexity of different algorithms using Big O Notation
• Describe what a logarithm is

• Define what recursion is and how it can be used.
• Understand the two essential components of a recursive function.
• Visualize the call stack to better debug and understand recursive functions.
• Use helper method recursion and pure recursion to solve more difficult probles.

• What is recursion? A process( a function in our case) that call itself

• In almost all program languages, there is a built in data structure that manages what hanppens when functions are invoked (It's named call stack).

  • About call stack
    • It's stack in data structure.
    • Any time a function is invoke it is placed (pushed) on the top of the call stack
    • When JS sees the returns **key workd or when the function ends, the compiler will remove(pop).
    • Brieftly
      • You're used to functions being pushed on the call stack and popped off when they are done.
      • When we write recursive functions, we keep pushing new functions onto the call stack!

• How recursive functions work?
  Invoke the same function with a different input ultil reaching to base case.

• How do we search? Given an array, the simplest way to search for an value is to look at every element in the array and check if it's the value we want. (called linear search)

• JS has search!

  • There are many different search methods on arrays in javascript:
    • indexOf
    • includes
    • find
    • findIndex

• Example :
  • Sorting numbers from smallest to largest
  • Sorting names alphabetically
  • Sorting movies based on release year
  • Sorting movies based on revenue

• Sorting is an incredibly common task, so it's good to know how it works.
• There are many different ways to sort things, and different techniques have their own advantages and disadvantages.
• Elementary Sort :
  1. Bubble sort.
  2. Selection sort.
  3. Insertion sort.
• Compare Bubble, Selection, Insertion sort

• Shortly:
  • Sorting is fundamental!
  • Bubble sort, selection sort, insertion sort, are all roughly equivalent
  • All have average time complexities that are quadratic
  • We can do better... but we need more complex algorithms!

• The sorting algorithms we've learned so far don't scale well.
• There is family of sorting algorithms that can improve time of complexity from O(n²) to O(nlogn).
• The more efficient algorithms are much less simple, and generally take a longer time to understand

• In order to implement merge sort, it's useful to first implement a function responsible for merging sort.
• Given two arrays which are sorted, this helper function should create a new array, which is also sorted, and consists of all of the elements in the two input arrays.
• This function should run in O(n + m) time and O(n + m) space and should not modify the parameters passed to it.\

• In order to implement merge sort, it's useful to first implement a function responsible for merging sort.
• Given two arrays which are sorted, this helper function should create a new array, which is also sorted, and consists of all of the elements in the two input arrays.
• This function should run in O(n + m) time and O(n + m) space and
• The order of element on either side of the pivot doesn't matter!
• The helper should do this in place, that is, it should not create a new array
• When complete, helper should return the index of the pivot.
• The runtime of quick sort depends on parts on how one selects the pivot
• Ideally, the pivot should be chosen so that it's roughly the median value in data set you are setting.
• For simplicity, we'll always choose the pivot to be the first element.

• Radix sort is a special sorting algorithm that works on lists of numbers
• It nerver makes comparisions between elements
• It exploits the fact that information about the size of a number is encoded in the number of digits
• More digits means the bigger number!

• Singly linked lists are excellent alternatives arrays when insertion and deletion at the beginning are frequently required
• Array contains a build in index, whereas Linked lists do not index.
• The idea of list data structure that consists of nodes is the foundation for other data structures like Stacks and Queues

• Doubly Linked Lists are almost identical to Singly linked lists except there is an additional pointer previous nodes.
• Better than Singly Linked List for finding nodes and can be done in half the time!
• However, they do take up more memory considering the extra pointer.

• Managing function invocations.
• Undo/ Redo
• Routing (the history object) is treated like a stack!

     Binary Tree is a data structure that consists of nodes an a parent/child relationship.
     The different between List and Tree are :
       List is linear
       Tree is nonlinear

• Root : The top node in a tree.
• Child : A node directly connected to another node when moving away from the Root
• Parent : The converse notion of a child.
• Siblings : A group of nodes with the same parent.
• Leaf : A node with no children.
• Edge : The connection between one node and another.

• HTML DOM
• Network Routing
• Abstract syntax tree
• Artificial Intelligence, Machine Learning
• Folders in Operation Systems
• Computer File Science

• Every parent node has at most two children
• Every node to the left of a parent node is always less than the parent
• Every node to the right of a parent node is always greater than the parent

• Two ways :
  • Breadth-first Search
  • Depth-first Search

• Trees are non-linear data structures that contain a root and child nodes
• Binary Trees can have values of any type, but at most two children for each parent
• Binary Search Trees are a more specific version of binary trees where every node to the left of a parent is less than it's value and every node to the right is greater
• We can search through Trees using BFS and DFS