Time Complexity in Algorithms

When you are running an algorithm, it takes some time to run. If your computer is super fast, then your running time would be so tiny fractions of a second, but that time can not be absolute zero. We can call that time as cost, since it's something like units. More running time, is more cost.

You can't guarantee that, Your Computer with some tasks running in background, will take the same time as mine; with the same tasks running in background. It's dependant on both of our computers' CPU, Memory and so on. But I can tell that, my computer almost* works in a similar manner, every time*.

So I calculate that cost and multiply it with some value for my computer, where as you can get that same cost and multiply it by some other value for your computer. Calculating that cost, is what we are about to do now.

So if we are going to calculate the cost, the following things matter in a code.

1. Statements
2. Blocks

Statements

If you are using a language such as Java, your statements are the ones that end with a semicolon (;).

statementOne;  statementTwo;
statementThree;
statementFour;

Each statement will have a minimum cost of 1, whereas the maximum cost is dependant on how that statement is structured. a System.out.println("Something"); or a similar statement will have a cost of 1. 

Blocks

Again if you are using Java, blocks are the ones surrounded by curly braces ( { } ). This is usually a group of statements.

{
  statementInBlock_One;
  statementInBlock_Two;   statementInBlock_Three;
}

Now let's talk about a thing called the input size. It is a term, that usually specifies the amount of data, in storage. You basically input the data, so you say it's input size. It's usually denoted by N. The storage is an array, arraylist or something like that. Parts of your algorithm (statements of algorithm), can depend on the input size, or not. How?

Let's say you are about to do something for each data item, that is stored. So that obviously depends on the input size. If you increase the input size, the total time spent on them will also be increased.

If you are not going to touch any of the data item, but just going to do something else, So that doesn't depend on the input size. Even if you increase the input size, total time spent would not change accordingly, because it's not going to touch data items!

So I would say, Some actions are dependant on the input size, and some are not.

Not Depended on Input Size

Actions (operations, assignments and etc.) that are not depended on N are normally having constant costs. That constant value can be any integer; as a single such action costs 1, and a series of such actions will cost some number of 1's = a constant.

Let's see some of them.

1. Variable Declaration & Variable Assignment

int i; // Line 1 : Declaring a variable. Cost = 1
i = 5; // Line 2 : Assigning a value to the variable. Cost = 1
i = N; // Line 3 : Assigning again. Cost = 1

- Line 1 : Even if you create a variable named i , or a variable named ironManIsAlive , we consider them as same. We only consider them as 'Creation of variable', rather than considering the names of the variables. That time (or cost) is going to be almost same, for each variable you are going to create like this. We take that as 1 for each such creation. Since only one variable is created here, the cost is 1.

- Line 2 : Even if you assign 5 to i or 555 to i, we are just worried about the 'assigning to the variable' part, rather than the value of the variable. So cost 1.

- Line 3 : Confused about the N appearing here? Read Line 2's statement again. Don't worry about the value of the variable. It's just another assignment, so cost 1.

So in total, this whole code will have a total cost of
1 + 1 + 1 = 3
This 3 just 3, even if you change the input size N.
That's independent of N!

2. Operations

int i; // Line 1 : we have seen this already. Cost = 1
i = 5 + 2; // Line 2
i = 4 * 7; // Line 3
i = 3 * 6 + 5; // Line 4
i += 50 // Line 5

Despite of the equal sign, counting the number of operations would tell us, how much cost is spent : expect the assigning. So at the end, we just add 1 for assigning and tell the total cost of that particular statement.

Basically, Count the number of operations. Each operator has Cost 1.

- Line 2 : We have one operation happening here, the addition, that has a constant cost 1. And there is another thing which spends time on, assigning to variable, that has a constant cost 1. So the total cost is 2 for this statement.

- Line 3 : Same as the above, 1 for multiplication, and 1 for assigning so totally 2.
- Line 4 : Here we have two operations and an assigning, so our costs are : 1 for multiplication, 1 for addition, and 1 for assigning, so totally 3.
- Line 5 : addition and assigning. totally 2.

So in total, this whole code will have a total cost of
1 + 2 + 2 + 3 + 2 = 10

3. Comparisons

if(5 == 2){// Line 1
 System.out.println("This is a statement. So Cost 1 FOR THIS LINE"); // Line 2
}
if(c >= b){ // Line 4
 System.out.println("This is a statement. So Cost 1 FOR THIS LINE"); // Line 5
}

- Line 1 : One comparison. Cost 1. But this condition is obviously false since 5 is not equal to 2, so we are not going into this condition and look about Line 2.
- Line 4 : >= is a single comparison, so Cost 1. We can't assure whether is it true or false, without knowing the values of c and b. So the worst case would be, getting it true and going into the condition (which is more work to the computer), so we count the statement that's executed when this condition is true, a cost 1.

So in total, this whole code will have a total cost of
1 (for the comparison 5==2) + 1 (for the comparison c>=b) + 1 (for the statement inside condition) = 3

4. Some other Cost 1's : String concatenation, return statement, System.out.print(),...

Depended on Input Size

Actions that are depended on N are usually loops and all. Let's see some of them.

1. WHILE loop

int i=1; // Line 1 : Cost 1
while(i <= N){ //Line 2
 System.out.println("Hey. I have Cost 1"); // Line 3 : Cost 1
 i++; // Line 4 : Cost 1
}

- Line 2 : When beginning, i is having value 1. N is a positive integer, let's assume. Now this comparison in Line 2 will happen several times : as follows

• 1st time : comparison happens. True, statements inside loop are executed
• 2nd time : comparison happens. True, loop is executed
• .....
• (N-1)th time : comparison happens. True, loop is executed
• Nth time : comparison happens. True, loop is executed
• (N+1)th time : comparison happens. FALSE!. Get out of the loop. Just after doing this comparison only, the loop exits.

So this comparison is done N+1 times. (consider i's starting value, and the condition whether is it < or <= carefully).

- Line 3 & Line 4 : Each of these are having costs, 1. These are inside the loop. Even if the comparison happens N+1 times, it's condition is true only for N times, which will run the loop only N times.

So in total, this whole code will have a total cost of
1 (for assign) + (N+1) (for comparisons) + (N * ( 1 + 1 )) (loop with 2 statements, running N times)
= 1 + N + 1 + 2N
= 2 + 3N

When you double the input, say now N is 2N. So this cost would be 2 + 3(2N) = 2+6N.
This is dependant on the input size!

2. FOR loop

for(int i=1 ; i<= N ; i++){ //Line 1
 System.out.println("Hey. I have Cost 1"); // Line 3 : Cost 1
}

Now here, the Line 1 is having more than one statements in it. statement i<=N is dependant on N and other two are not. So let's break them down. We can convert every such for loop, into a while loop, as follows

int i=1; // Line 1 : Statement 1 in above = Cost 1
while(i <= N){ // Line 1 : Statement 2 in above = Cost N+1
 System.out.println("Hey. I have Cost 1"); // Line 3 in above = Cost 1 (this runs N times)
 i++; // Line 1 : Statement 3 in above = Cost 1 (this runs N times)
}

Seems familiar right? Yes! It's the same WHILE loop we saw above in 1. ! So the cost is now 2 + 3N. Dependant on the input size!

Always note that, wherever we see a N, it's the input size. Unless the requirement / the question says to consider some other letter

Those were the building blocks. Now we should be able to calculate the time complexity of a more complex code. Shall we give out two tries?

TODO 1 : 

int i,j; // Line 1
i = 6; // Line 2
j = 0; // Line 3

while(j < N+1){ // Line 5
 i = j; // Line 6
 j++; // Line 7
}

Line 1 :- 2
Line 2 :- 1
Line 3 :- 1
Line 5 :- N+2 (0,1,2,...,N,N+1)
Line 6 :- 1 * (N+1)
Line 7 :- 1 * (N+1)

Total cost :
2 + 1 + 1 + (N+2) + 2 (N+1)
= 4 + N + 2 + 2N + 2
= 8 + 3N

TODO 2 : 

int j; // Line 1
j = 2; // Line 2

for(int i=j ; i < N ; i++){ // Line 4
 System.out.println("TODO"); // Line 5
}

Line 1 :- 1
Line 2 :- 1
Line 4 : Statement 1 :- 1
Line 4 : Statement 2 :- N-1 (2,3,4, ... , N-1, N)
Line 4 : Statement 3 :- 1 * (N-2)
Line 5 :- 1 * (N-2)

Total cost :
1 + 1 + 1 + (N-1) + (N-2) + (N-2)
= 3 + (N-1) + (N-2) + (N-2)
= 3 + 3N - 5
= 3N - 2

Just make sure to defend the loops especially, even though they are tricky!
Sharing is Caring!
Good Luck!