time complexity

We will represent the time function T(n) using the "big-O" notation to express an algorithm runtime complexity. For example, the following statement

T(n) = O(n²)

says that an algorithm has a quadratic time complexity.

Constant Time: O(1)

An algorithm is said to run in constant time if it requires the same amount of time regardless of the input size. Examples:

• array: accessing any element
• fixed-size stack: push and pop methods
• fixed-size queue: enqueue and dequeue methods

Linear Time: O(n)

An algorithm is said to run in linear time if its time execution is directly proportional to the input size, i.e. time grows linearly as input size increases. Examples:

• array: linear search, traversing, find minimum
• ArrayList: contains method
• queue: contains method

Logarithmic Time: O(log n)

An algorithm is said to run in logarithmic time if its time execution is proportional to the logarithm of the input size. Example:

• binary search

Quadratic Time: O(n²)

An algorithm is said to run in logarithmic time if its time execution is proportional to the square of the input size. Examples:

• bubble sort, selection sort, insertion sort, quick sort.