Time Complexity? - prasanna-kamath/Resources GitHub Wiki

Have no clue about these notations?

O( n ), O( n^2 ), O( n*log(n) ), Ω(n), ...

They are called time complexity notations and are extensively used to represent the amount of time required for a program or a function to complete its execution. Let's understand it's parts first:

  1. first part of these notations contain any of these 3:

O

(big O)

  • This represents the performance of the program in worst case scenario (frequently used)

Ω

(Omega)

  • This represents the performance of the program in best case scenario (Hence, used very rarely)

Θ

(Big Theta)

  • This represents the Average performance of the program.
  1. Next part: what is n?

Yes, you probably guessed it, it is number of computations your program makes during execution.

Let's take and example to make sense of all this:

  • Consider you have 2 integers and you write a program to add them and display the output. What is it's time complexity?
    • Since you already have 2 numbers and you are just adding them, we can do the addition with 1 computations i.e, a + b where a and b are values to be added.
    • Hence, time complexity for this addition is 1 even in worst case(since the numbers are already in hand), it is represented as O(1)
  • Let's take another example: What is time complexity for searching an element in 1-Dimensional Array(linear search)?
    • Let's see, in worst case the desired element is found at the end of the array.
    • So, if n is the size of the array, for worst case number of computations required to find the desired element is n
    • You guessed it right, time complexity for linear search program is O(n). This means that, time required to find an element in an array increases linearly with increase in number of elements in the array.
    • So, what is the big deal?. Imagine, if google was using linear search to help you complete your assignments then how much time it would have taken to give you the results. This is the reason for need of Time complexity analysis for a program or algorithm

What if the program was adding elements in an array?

Will it be O(n) because it involves 1-D array or O(n+1) because it involves addition task along with 1-D array?

  • Time complexity actually will be n+1 but we ignore the one because as n increases, the contribution 1 to the overall execution time becomes negligible.Hence, the answer is O(n) and not O(n+1)
  • Similarly, time complexity of a program whose outcome is a Quadratic equation will be O(n^2) and so on.

Now that you have enough introduction about some time complexities, Go through these resources for proper understanding of time complexity analysis of an algorithm: