Big O Notation- Understanding Time complexity with C-sharp Examples

Hi Guys, Today we'll be talking about a very fundamental part of computer science and programming in general; Time complexity in Big O notation

First of all, we need to ask some questions;

What is Big o notation: Big O notation in its simplest form is simply the way we measure the efficiency of an algorithm as input grows. Thats it.

What is Time Complexity: Time Complexity is the amount of time it takes an algorithm to run completely given a specific input or sample size.

We'll talk about the most common time complexities we have in programming;

• Constant Time (O(1))
• Linear Time (O(n))
• Quadratic time (O(n^2))
• Logarithmic time (O(log n))

Let's go through these one by one:

Constant Time: An algorithm is said to run in constant time if it runs in the same time regardless of the input size. For example, you are asked to write a function that returns the first element in an array, so you'll have something like

public int FirstArrayElement( int[] numbers){
return numbers[0];
}

Great, so it does not matter if there are 5 elements or 50 elements in the numbers array. It will always run in the same time, hence constant time.

Linear time: An algorithm is said to run in linear time when the time it takes to run is directly proportional to the input size. A good example is if you are asked to print every element in an array.

public void PrintElements(int[] numbers){
    for(int i =0; i < numbers.Length; i++){
    Console.WriteLine($"This is element {i}")
    }
}

So, if the numbers array has 5 elements, our algorithm will go around 5 times, if it has 10 elements, our algorithm will go around 10 times, and so on.

Quadratic time: Algorithms with nested for loops (i.e. a for loop within another for loop) are said to run in quadratic time. For example, if you are asked to find two numbers in our numbers array that add up to 10, we can write an algorithm in Quadratic time like this

public int[] SumTwoNumbers(int[] numbers){
int[] nums = new int[2];
for(int i =0; i < numbers.Length; i++){
    for(int j =1; j < numbers.Length; j++){
        if(numbers[i] + numbers[j] == 10) 
        nums[0] = numbers[i];
        nums[1] = numbers[j];
    }
}
return nums;
}

So from this example above, although it is not efficient, it shows how quadratic time works. where if we have 5 elements in the numbers array, our algorithm with run 5^2 which is 25, and if there are 10 elements in the array our algorithm will go around 10^2 which is 100 times. And so on.

Logarithmic time: An algorithm runs in logarithmic time if it takes to run is proportional to the logarithm of input/ sample size. A good example of an algorithm that implements logarithmic time complexity is binary search. Basically in binary search, for every round trip it makes, the search interval is divided in half.

public bool BinarySearchchek(int[] numbers){
int low = 0;
int high = numbers.Length - 1;
int mid = (low + high)/2;
while(low <= high){
 if(numbers[mid] == 10) return true;
 if(numbers[mid] < 10 ) low = mid + 1;
 if(numbers[mid] > 10) high = mid - 1;
 mid = (low + high)/ 2;
}
return false;
}

So basically, as the while loop runs, depending on the condition, we either increment the low variable or decrement the high variable, and then recalculate the mid to run in the loop again.

Those of some of the most popular time complexities we have in programming and with practice and a little more learning, you should be able to see when an algorithm runs in a specific time.

Happy coding everyone.