Big O in Data Structure

What is the importance of the Big O notation?

Big O notation is important for a variety of reasons:

• Evaluates the efficiency of algorithms.
• Describes the amount of time or space required as the input size grows.
• Allows for more efficient algorithm comparison.
• Understands scalability and predicts performance as input size increases.
• Improves code and improves overall performance.

How Can Big O Notation Be Determined?

The following are the processes to determine Big O notation:

1. Define the dominant term.
2. Identify the Order of Growth
3. Use the Big O Notation
4. Simplify Notation (Optional)

What is Asymptotic Analysis in Data Structure?

• Asymptotic analysis is a technique for analyzing how an algorithm behaves or performs as the input size changes.
• For example: When the input array is in reverse order, bubble sort takes the maximum amount of time (quadratic) to sort the items, which is the worst case case.
• However, when the input array is already sorted, the algorithm's temporal complexity is linear, which is the best-case case.
• When the input array is neither sorted nor reversed, it takes average time, also known as the average case.
• These durations are represented by asymptotic notations.

Asymptotic notations for algorithmic complexity analysis

There are three basic asymptotic notations for analyzing algorithm complexity. They are as follows.

1. Big-O notation
   
2. Omega notation
3. Theta notation

1. Big-O Notation (O-notation)

Big O notation represents the upper bound of an algorithm's running time or the largest amount of time it takes to perform its operations. As a result, it provides a worst-case complexity for an algorithm.

2. Omega notation (Ω-notation)

The omega notation (Ω-notation) represents the bottom bound of an algorithm's running time. Thus, it provides an algorithm's best-case complexity. It determines how fast an algorithm can run.

3. Theta notation (Θ-notation)

Theta notation represents the upper and lower bounds of an algorithm's runtime. In real-world issues, an algorithm does not perform worst or best; rather, it varies between the worst and best cases, giving the method's average-case complexity.

Big-O Notations

• O(1) – Constant
• O(logn) – Logarithmic
• O(n) – Linear
• O(nlogn) – Linearithmic
• O(nc) – Polynomial Like Quadratic (n2), Cubic (n3) etc.
• O(cn) – Exponential (2n)
• O(n!) – Factorial

O(1) - Constant Runtime Complexity

It always takes the same amount of time to be executed. The complexity remains constant regardless of the input size. For example, accessing an element of an array at a specific index. This will only execute once and is a constant.

O(logn) – Logarithmic Runtime Complexity

The complexity increases linearly as the input increases exponentially. As input size increases, O(log n) notation outperforms O(n) and O(n²).

O(n) - Linear Runtime Complexity

The time required to perform the method is directly proportional to the input size n. Complexity increases linearly over time as the number of inputs increases, implying that the more inputs, the greater the complexity.

O(nlogn) - Linearithmic Runtime Complexity

The time required to execute the method will increase at a rate that can vary from linear to exponential. Slower than exponential, but faster than linear.

O(n^c) - Polynomial Runtime Complexity

The time required to run the algorithm is directly related to the power (c) of the input size n. It is the square of the input size n, similar to the Quadratic equation.

O(cⁿ) - Exponential Runtime Complexity: O(2ⁿ)

The time required to perform the method doubles with each addition to the input dataset. Usually, these are recursive algorithms that solve two smaller issues of size n-1 iteratively to answer a larger problem of size n.

O(n!) - Factorial Runtime Complexity

The runtime for computing factorials increases exponentially with the amount of inputs. For example, 5! is 120, and 10! is 3628800. This algorithm grows swiftly and has the worst temporal complexity.

Multiple Runtime Complexity

In the case of several difficulties, take the worst case, which will be your algorithm complexity.

Big-O Notation Algorithms Examples

• Constant O(1): Accessing an element in an Array by index number.
• Linear O(n): Linear Search.
• Logarithmic O(long): Binary Search.
• Linearithmic O(nlogn): Heap Sort, Merge Sort.
• Polynomial O(n^c): Bubble Sort, Selection Sort, Insertion Sort, Bucket Sort.
• Exponential O(c^n): Tower of Hanoi.
• Factorial O(n!): Permutations of a string, Brute force Search algorithm for Traveling Salesman Problem.

Problem-Solving Methods in Data Structure

• Single and Nested Loops
• Decrease and Conquer, Divide and Conquer, Transform and Conquer
• Binary Search
• Two Pointers and Sliding Window
• Breath First Search and Depth First Search
• Data Structures: Stack, Queue, Hash Table, Trie, Heap, BST, etc.
• Dynamic Programming
• Greedy Algorithms