Complexity

Question 1

Time complexity

Answer 1

Is a measure of the amount of time it takes for an algorithm to run as function of the input size. It provides an estimate of how the algorithms runtime grows as the input size increases. It usually expresses by big O notation.

Question 2

O(1)

Answer 2

Constant time. The algorithms runtime remains content regardless of the input size.
Example:
Accessing a specific index within an array: arr[0]

Question 3

O(log n)

Answer 3

Logarithmic time. The algorithms runtime grows logarithmically with the input size.
Example: binary search tree

Question 4

O(n)

Answer 4

Linear time. The algorithms runtime grows in direct proportion to the size of the input data.
Example: for loop

Question 5

O(n log n)

Answer 5

Linearithmitic time. The algorithms runtime grows in proportion to the product of the input size and its logarithm.
Example: merge sort

Question 6

O(n^2)

Answer 6

Quadratic time. The algorithms runtime grows quadratically with the input size.
Example: nested for loops

Question 7

O(2^n)

Answer 7

Exponential time. The algorithms runtime grows exponentially with the input size.
Example: double recursive method