• 복잡도의 점근적 상한
  • "최대 이만큼의 시간이 걸린다."

  • 복잡도의 점근적 하한
  • "최소 이만큼의 시간이 걸린다."

  • Big-Oh와 Big-Omega가 같은 경우에 사용
  • n이 증가함에 따라 동일한 증가율을 가진다.
  • "항상 이만큼의 시간은 걸린다."

  • k개의 비트를 사용하면 **0부터 2^(k-1)**까지 표현 가능
  • n을 표현하기 위해서는 몇 개의 비트가 필요할까
  • 2^(k-1)-1 >= n이 성립해야 한다.
  • k >= log(n+1)이므로 약 logn 비트가 필요

  • 2의 몇 승이 n이 되느냐의 답
  • n을 표현하는 데에 몇 비트가 필요한가
  • 1로 시작해서 계속 두 배를 할 때 몇 번 해야하는가
  • n을 2로 계속 나눌 때 몇 번 나누면 거의 1이 되는가