Time Complexity

Time complexity is an important part of algorithms in programming. By using time complexity, we can estimate how much time is needed for a code to run. Usually 3 symbols are used to denote the time complexity. They are big O notation, omega and theta. omega represents best case scenario, theta represents average case scenario and big O notation represents worst case scenario. Mostly during analyzing time complexity, worst case scenarios are calculated. That's why big O notation is used. There are some notations for time complexity like O(1), O(n), O(n^2), O(logn), O(nlogn) etc.

Firstly, we will talk about O(1). This actually means that our code will run for constant time. For example, we can write the python code likex = 9. This line of code will have a time complexity of O(1) which is constant. Similarly, if we write the code

x = 9
y = 5

what will be the time complexity here? In this code, each line has a time complexity of O(1).As each line of this python code has a time complexity of O(1) so will the time complexity of the code be O(1+1) which is O(2)?No, it will still be O(1) that is because O(2) is also a constant time and O(1) is used to represent constant time.

But what if we have a loop in our code? Let's write a code for that.

for i in range(10):
   print(i)

Here the print statement has a time complexity of O(1). In this for loop the print statement will run 10 times.So, the time complexity will be O(10) as the loop will run 10 times. But what if the loop runs n times? Then the time complexity will be O(n). So, for a single loop the time complexity will be O(n). But what if there are 2 loops in our code. For example:

for i in range(n):
  print(i)
for j in range(n):
  print(j)

Here, the time complexity will be O(n+n) which is O(2n). But for writing time complexity we ignore the constants. So the time complexity for this code will also be O(n).

Besides, we will talk about another time complexity which is O(n^2). This time complexity is for nested loops. For example:

for i in range(n):
  for j in range(n):
     print(i,j)

In this code as there is a nested for loop the code will run O(n*n) times which is O(n^2) times. In this case also if there is the constant then we will remove it.What will be the time complexity for this code?

for i in range(2n):
   for j in range(n):
       print(i,j)
for a in range(n):
  print(a)

In this code, will the time complexity be O(2*(n^2)+n)? No, still the time complexity of the code will be O(n^2). The reason is that we ignore constants in writing big O notation. So, 2 will not be written in big O notation. But another question arises which is why won't the time complexity be O(n)? The reason is we always take the highest power of the equation we get in big O notation.That's why the time time complexity of the code is O(n^2).