Big O Notation

Question 1

Space complexity

Answer 1

refers to the amount of physical memory that an algorithm requires to complete.

Question 2

Time complexity

Answer 2

the number of operations an algorithm requires to complete.

Question 3

Big O notation

Answer 3

1. way of describing the time complexity of an algorithm.
2. how much time is needed for an algorithm to complete its work with a given input
3. help us understand how a given algorithm will perform in the best-case scenario, in the worst-case scenario, and on average.

Question 4

linear relationship

Answer 4

The time complexity of the algorithm grows in direct, linear proportion to the size of the input.

Question 5

Constant time complexity

Answer 5

type of Big O Notation
No matter the size of your input, the algorithm will take the same amount of time to complete.
examples:
1. accessing an array item
2. performing basic arithmetic operations (e.g., adding 2 numbers)

Question 6

Logarithmic time O(log(n))

Answer 6

type of Big O Notation
cut the problem size in half each round through.
While logarithmic time complexity algorithms do take longer with larger inputs, running time increases slowly.

Question 7

Linear time O(n)

Answer 7

type of Big O Notation
Algorithms with linear time complexity (O(n)) have running times that are directly proportional to the size (n) of the input.

Question 8

Polynomial time O(n^k)

Answer 8

• An algorithm with polynomial time complexity has a running time that would be some input size n raised to some constant power k.
• The easiest way to understand polynomial time complexity is with nested loops.
• An algorithm that requires 2 levels of looping over an input would be O(n^2) while one requiring 3 levels of looping would be O(n^3). In both cases, we have polynomial time complexity.

Question 9

Exponential time O(2^n)

Answer 9

• Algorithms with exponential time complexity (O(2^n)) have running times that grow rapidly with any increase in input size.
• For an input of size 2, an exponential time algorithm will take 2^2 = 4 time.
• With an input of size 10, the same algorithm will take 2^10 = 1024 time, and with an input of size 100, it will take 2^100 = 1.26765060022823 * 1030 time.