# RECURSION

`Function recursive(...parameters){  // base case  if(더이상 쪼개지지 않는 상태){    return  }  // recursive  // 현재 단계에서 처한 문제들 = 경우의 수 = 선택의 가짓수  for(let i=0){    if(조건 달성) recursive(...parameters)  }}`

# Big O notation

• Big O (O): 최악의 경우
• Big Omega (Ω) : 최상의 경우
• Big Theta (Ө): 최악과 최상의 중간
• DROP CONSTANTS!

constant: array look up, hash table insertion

logarithmic: binary search tree

linear: for loop(up to n)

quadric: constant time operation inside two nested for-loops

exponential: recursion(fibonacci)

• O(logn)이 O(n)보다 항상 빠르지는 않음. n=1일 때 예외

# Array

• Lookup(position): O(1)
• Assign: O(1)
• Insert: O(n)
• Remove: O(n)
• Find(value): O(n)

• Lookup: O(n)
• Assign: O(n)
• Insert: O(1)어디에 넣을건지 알면 // 모르면 O(n)
• Find(value): O(n)

• Lookup: O(n)
• Assign: O(n)
• Insert: O(1)
• Remove: O(1)
• Find(value): O(n)

# Binary Search Tree

• As above, it is unbalanced, which means depth is more than 1 between parent and both children
• in order to be balanced, it is better to re-balance as node inserted
• better to user BST over sorted array because trees occupy non-contiguous memory

reference:

## More from Joo Hee Kim

Consistency achieves everything https://github.com/paigekim29