Time complexity, Space complexity

• Time complexity Consider worst cases! Using Asymptotic Analysis(점근적 접근): 최고차항만 의미 있다.

  • Big-O : Upper bound, worst case

    

    Then T(n) ㅌ O(f(n))

  • Big-Theta: Equal, Avg case

    

  • Big-Omega: Lower bound, Best

    

• Typical Growth Rate

  

  • 1 Hash Table avg Search
  • logn BST avg search Balanced BST search Heap tree insert, delete
  • n BST worst search Hash Table worst search Heapify ST
  • nlogn Quicksort avg Merge sort Dijkstra
  • n^2 Quicksort worst Bubble, Selection, Insertion