Big O

• What does Big O Notation measure?

  Steps and memory usage change with data
• How does a linear algorithm grow?

  It grows in proportion to the amount of data
• What characterizes an exponential growth rate?

  Rate increases at the rate of $k^n$
• What does constant time complexity mean?

  Time does not change with more elements
• How does polynomial time complexity behave?

  Time increases as a polynomial function of elements
• What does logarithmic time complexity indicate?

  Time increases at a rate of $\log_k n$
• What are the types of Big O Notation complexities?


  • Constant O(1)
  • Logarithmic O(log n)
  • Linear O(n)
  • Polynomial O(n^k)
  • Exponential O(k^n)
• How does logarithmic time complexity compare to linear?

  It increases more slowly than linear time
• How does linear time complexity behave when elements double?

  Time needed also doubles
• What does polynomial time complexity indicate when elements double?

  Time increases by a factor of $k$
• How does exponential time complexity behave?

  Time increases rapidly as elements increase
• How does memory usage relate to Big O Notation?

  Memory usage can also be evaluated with Big O
• How can Big O Notation be used in algorithm comparison?

  • Evaluates performance of algorithms
  • Compares time and memory usage
  • Provides impression of performance variation with data
• What is the time for $\log_2 n$ when $n =$$1$?


  1
• What is the time for $\log_2 n$ when $n =$$2$?


  2
• What is the time for $\log_2 n$ when $n =$$3$?


  2.58
• What is the time for $\log_2 n$ when $n =$$4$?


  3
• What is the time for $\log_2 n$ when $n =$$5$?


  3.32
• What is the time for $\log_2 n$ when $n =$$6$?


  3.58
• What is the time for $\log_2 n$ when $n =$$7$?


  3.8
• What is the time for $\log_2 n$ when $n =$$8$?


  4
• What is the time for $\log_2 n$ when $n =$$9$?


  4.16
• What is the time for $n^2$ when $n =$$1$?


  2
• What is the time for $n^2$ when $n =$$2$?


  4
• What is the time for $n^2$ when $n =$$3$?


  9
• What is the time for $n^2$ when $n =$$4$?


  16
• What is the time for $n^2$ when $n =$$5$?


  25
• What is the time for $n^2$ when $n =$$6$?


  36
• What is the time for $n^2$ when $n =$$7$?


  49
• What is the time for $n^2$ when $n =$$8$?


  64
• What is the time for $n^2$ when $n =$$9$?


  81
• What is the time for $2^n$ when $n =$$1$?


  2
• What is the time for $2^n$ when $n =$$2$?


  4
• What is the time for $2^n$ when $n =$$3$?


  8
• What is the time for $2^n$ when $n =$$4$?


  16
• What is the time for $2^n$ when $n =$$5$?


  32
• What is the time for $2^n$ when $n =$$6$?


  64
• What is the time for $2^n$ when $n =$$7$?


  128
• What is the time for $2^n$ when $n =$$8$?


  256
• What is the time for $2^n$ when $n =$$9$?


  512