Time complexity banter with software engineers

 As much as the name of software engineer sounds fancy, its work is also very complicated.

A problem can be solved in many ways. But it is necessary to think about how long that problem is to be solved. Some examples will help to understand.

For example, suppose you are given some number -

1,2,3,4,5,6,7,8,9,10,11,13,17,19,51,73, 93, 101…….. N

In the above example, numbers are given from 1 to N. And the numbers are sorted. That is, arranged from small to large.

Now if you are given a number and asked if this number is among those numbers write a program like this. Now how can the work be done? This can be done by simply applying a linear search.

What is linear search?

Linear search is where you check all the numbers from the beginning to the end. If any of these numbers is equal to the number we are looking for then we will understand that the number has been found. And if any number does not match then you must understand that the number you are looking for is not in those numbers.

Now we are talking about how much time linear search takes.

Now suppose you are given a number that starts with 1. So in this case, by checking the first number, it is understood that the number has been found. That is 1 operation we found the number. This is the best case. Since we have 1 operation here, we can say its time complexity is (big O)O(1). But how many operations would be required to find the last number?

1,2,3,4,5,6,7,8,9,10,11,13,17,19,51,73, 93, 101…….. N <= we don't know how many numbers are there. If there are N numbers here then N operations have to be performed to find the last number. Then its time complexity will be (big O)O(N).

If there are 1 crore, 2 crores or more numbers, then 1 crore, 2 crores or more operations have to be carried out.

And when calculating the time complexity, the worst case is counted. That is, if the linear search is applied, its time complexity will be O(N) and it can be very expensive.

Now, something needs to be done to reduce its time complexity. Since the numbers are sorted from smallest to largest then we can apply binary search here. It is not necessary to understand what binary search is, for now, it will be convenient to understand with an example.

Suppose we have N numbers and N = 10

That means we have 10 numbers

101, 103, 109, 111, 124, 138, 147, 152, 177, 183

Now how can we apply binary search to these numbers? We can think of the positions of the numbers that are here. Below are the numbers with positions.

Numbers	101	103	109	111	124	138	147	152	177	183
positions	1	2	3	4	5	6	7	8	9	10

Now if you are allowed to search whether the number 183 exists. So how can you think about binary search? Let's see

We can let the start position be x and the end position is y.

Then x = 1 and y = 10

And the mid position of x and y can be found as mid and mid = (x+y)/2

In the first operation we get mid = (1+10)/2 = 5.5 = 5 (we will always take the floor value of a number)

What is the floor value of 5.7

The floor value of 5.7 will be 5 

The floor value of 8.1 will be 8

That is, to put it simply, I will drop the part after the decimal.

So in the first operation, we get mid = 5

Now we have to see if the number in position 5 is equal to 183

If it is equal then I got it. If you don't get it, you have to see if the number in the 5th position is smaller or bigger than 183. It looks like there are 124 in the 5th position. This number is smaller than 183. So now what we need to do is to increase the starting position by 1 from mid.

So now x = mid + 1 = 6 and y = 10

Then in the second operation we get mid = (x + y)/2 = (6+10)/2 = 8

8th position has 152 which is less than 183.

Then again start position should be set to mid + 1.

So now x = mid + 1 = 8+1 = 9 and y = 10

Now in the third operation we get mid = (x + y)/2 = (9+10)/2 = 9

9th position has 177 which is smaller than 183.

Then again start position should be set to mid + 1.

So now x = mid + 1 = 9+1 = 10 and y = 10

Now in operation number 4 we get mid = (x + y)/2 = (10+10)/2 = 10

The 10th position has 183 so we find 183.

That is, we found the number 183 in only 4 operations.

Our number here was N = 10

And it took us 4 hours to find a number

Its time complexity will be O(log N) <= showing how

If we write log base 2(N) then it will be log2(10) = 3.32192809 = 3 [we have taken floor value]

Then it can be written as O(logN+1) <= where 1 is the constant value and the constant value is not counted while calculating time complexity.

So the time complexity of this binary search will be O(logN).

There are many more. I tried to explain with a very simple example that a software engineer has to think about time complexity while writing a program. Then while solving many problems, it is seen that it may take a few hours or a few months, or in some cases even years to solve that problem.

So this was a small attempt to discuss time complexity.