Time Complexity

An algorithm’s time complexity if often expressed using big O notation. Below are some common types of algorithmic time complexity.

O(1) — With constant time complexity, as the input size grows, the number of steps remains the same. This is the most desirable type of time complexity. Looking up an item at a specific index of an array is an example of constant time. No matter how large the array, the lookup is a single operation.

O(log n) — With logarithmic time complexity, the number of steps increase as the input size increases, but at a slower rate as the size grows larger and larger. Binary search is an example of logarithmic time because we can divide the problem in half with each iteration. As we double the input size, only one additional step is required.

O(n) — With linear time complexity, the size of the input and the number of steps grow proportionally. Iterating through an array is an example of linear time because each additional item in the array requires one additional iteration.

O(n^2) — With quadratic time complexity, the number of steps is proportional to the square of the input size. An example of quadratic time is when we have a loop inside of a loop. If we iterate through an array of items, and on each iteration we iterate through all items in the array again, that would be quadratic time complexity. A loop inside a loop inside a loop would be O(n^3).

O(C^n) — With exponential time complexity, the number of steps increases exponentially with each increase of input size. This might be fine for very small input sizes, but as input size grows larger and larger, the time complexity may quickly become unacceptable. An example of exponential time would be a recursive solution to find the nth fibonacci number.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s