Big-O-Notation Form

What is Big-O-Notation

Big-O Notation measures how long it would take to locate an item according to the size of the item list and the manner in which it is searched.

O(n)

This time complexity means that as the number of items in search increases, so does the number of items we must check before finding the item we seek. A linear search is an example of this. O(n) also known as linear time complexity. We assume the worst-case scenario assumption. Adding items to a sequential array has an O(n) time complexity, as does searching for items in a stack, because they are not in any particular order, requiring you to go through each individual item. Traversing items in a binary tree and for and while loops is also O(n).

O(1)

O(1) is also referred to as a constant time complexity. If an item was at the beginning of the array in a linear search, the time complexity would be O(1). If we knew where the item was in the list, it would also be O(1). Pushing and popping items to and from a stack would be O(1). Hashing is also O(1) as long as there are no synonyms(duplicate items). If there are its O(n) since the item has to be found in the overflow.

To learn more about linear Search, click me.

O(Log n)

A binary search would have a time complexity of O(Log n). This is because in a binary search, we always half the list. Inserting items into a binary tree and searching items in a binary tree is also O(Log n). Halving data typically tends to be O(Log n).

O(n^2)

Because bubble sort and insertion sort use nested loops, they are O(n2). Nested loops are typically O(n^(number of loops)). Recursive algorithms are typically O(2^n).