Algorithms study

Big O

O(1) - linear O(log n) - logarithmic O(n) - linear O(n logn) - linearithmic O(n^2) - quadratic O(2^n) - exponential O(n!) - factorial

https://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly

Data structures

  1. stack
  2. queue
  3. linkedlist
  4. skiplist - access, search, insert, delete -> AVG: O(log(n)) Worst: O(n)
  5. binary search tree - access, search, insert, delete -> AVG: O(log(n)) Worst: O(n)

trees

traversal

  • depth first ->preorder (root, left, right), inorder (left, root, right) , postorder (left, right, root)
  • breadth first ->

def search_recursively(key, node):

if node is None or node.key == key: 
    return node
if key < node.key:
    return search_recursively(key, node.left)
else:
   return search_recursively(key, node.right)

graph

  • depth first search - Space complexity - O(mn), Time complexity - O(nm) -> stack
  • breadth first search - Space complexity 2(m+n), Time complexity - O(n*m) -> queue