What is computational complexity and Big O part 2?

In a previous blog, I wrote about the two-pointer algorithm, but I didn’t dive into how efficient it is as the input size grows. Today, let’s explore how to measure the efficiency of an algorithm. Before revisiting the two-pointer algorithm, it’s important to understand computational complexity and Big O notation. (Check out part 1 of computational complexity and Big Ohere)

Lastly we covered Constant O(1), Logarithmic O(Log n),
Today we will be covering Linear O(n), Log linear O(n Log n), Quadratic O(n²) and Exponential O(2n).

In the simplest sense, linear refers to something extending in a straight line. In terms of computational complexity, if you were to graph the relationship between the input size n and the number of operations, a linear time complexity graph would form a straight line.

What this means is: the number of operations scales directly with the size of n.

Let’s make this more relatable:
Imagine you’re a footballer with 10 balls. Your task is to kick each ball once. Here’s the math:

Balls: 10
Operations (kicks): 10

Since the number of operations (kicks) matches the number of balls, the complexity is linear — it scales 1:1 with the input size.

What are some operations you can do with Linear
1.Copying elements
2. Inserting or deleting items
3. Iterating through a dataset

The algorithm here will be
1. Linear search algorithm

Now, things get a bit more interesting. Log-linear complexity combines two behaviors:

• Linear O(n):We process nnn items.

• Logarithmic O(log⁡n):For each item, we perform a logarithmic operation.

Let’s say you have two tubes of balls. You want to compare every ball in Tube 1 with its counterpart in Tube 2.

• Searching Tube 1 takes O(n).

• For each ball in Tube 1, finding its counterpart in Tube 2 takes O(log⁡n).

Multiply these together, and you get O(nlog⁡n).

Properties of Log linear

1. For each operation of the input data has logarithmic time complexity

1. Sorting a list of elements

Algorithms

1. Merge sort

2. Heap sort

3. Cube sort

First remember Big O notation classify algorithms according to how their runtime or space requirements grow as the input size grows.

The purpose of reminding you this is to understand how the quadratic time grows as the input size grows.

Withquadratic complexity, the runtime scales as the square of the input size n: n².

Imagine nested loops:

• The outer loop runs nnn times.

• For every iteration of the outer loop, the inner loop also runs nnn times.
  This results in n×n=n² operations.

Properties of quadratic

1. Perform a linear time operation on each value of the input data.

Operations

1. Quadratic algorithms typically involvenested loops, where each loop depends on the input size.

Algorithm
1. Bubble sort
2. Tree sort
3. Selection sort
4. Insertion sort
5. Bucket sort
6. Quick sort

Remember what Big O notation does (Classify algorithm according to how their runtime and space requirements grow as the input size data grow).

Property
For exponential the growth doubles on each addition to the input data set

Think of theTower of Hanoiproblem orRecursive Fibonacci. Every time you add a disk (or an element), the number of operations required doubles.

Algorithm

Recursive Fibonacci

Wrapping up
Understanding computational complexity is key to writing efficient algorithms. By analyzing how the runtime grows with input size, you can predict performance and make better choices.

Next time, we’ll go deeper into these algorithms and see some practical examples.

Follow me onGithub
Check out myPortfolio.
Contact me for any collaboration in my Portfolio
Check outmy blogs from my Portfolio