Mastering Time and Space Complexity – A Comprehensive Guide

Time and Space Complexity

Time and space complexity are used to measure algorithm efficiency.

Complexity

• Complexity is a measure of how resource requirements change as the size of the problem gets larger.
• The higher the complexity of the problem, the lower the performance.

Algorithm Operations

When computing a program, these are the fundamental operations it carries out.

• Arithmetic operations.
• Read operations.
• Assignment operations.
• Write operations.
• Test conditions.

Performance

• Performance is measured along with resource consumption, and code consumes a variety of resources.
• Improving code performance beyond a certain point involves a trade-off.

Measures of performance

• Time: The amount of processing or number of operations the code has to perform to accomplish its objective.
• Space: Both the disk space and the memory that code needs for persistent storage during runtime.
• Network: The bandwidth code is used to pass information to clients or other machines.

Time complexity

time required to analyze a given problem of particular size is known as the time complexity.
Time complexity depends on the following factors:

• Size of input data.
• Hardware.
• Operating system.
• Programming language used.

Time complexity depends on two components

• Fixed part: compile time.
• Variable Part: Run time dependent on problem instance. Run time is usually considered, and compile time is ignored.

Ways to measure time complexity

Step count: count the number of program steps.

1. Comments are not evaluated, so they are not considered a program step.
2. In the while loop, steps are equal to the number of times the loop gets executed.
3. In a for loop, steps are equal to the number of times an expression is checked for a condition.

Space Complexity

The amount of memory required to solve a given problem of particular size is called space complexity.
The space complexity  depends on two components:

• Fixed part: It is needed for instruction space. i.e byte code, variable space constant space, etc.
• Variable part: Instance of input and output data.

Formula

space(s) = fixed part+ variable part.

How do I find complexity??

It depends on the following statements:

• Sequence of statements.
• if-then-else statements.
• for loops.
• Nested loops.

Sequence of Statements

statement 1;
statement 2;
...
statement n;

By adding the times for all statements, one can determine the total time.

total time = time(statement 1) + time(statement 2)+ ...+ time(statement k)

If each statement is simple, then the time for each statement is constant, and the total time is also constant: O(1).

if-then-else statements

if(condition){
  sequence of statements1
}
else{
 sequence of statements2
}

Here, either sequence of statements1 will execute, or sequence of statements2 will execute. Therefore, the worst-case time is the slowest of the two possibilities: max(time(sequence 1), time(sequence 2)).
Example:
if sequence 1 is O(N) and sequence 2 is O(1), the worst-case time for the whole if-then-else statement would be O(N).

for loops

for (i=0; i<N;i++){
sequence of statements
 }

The loop executes N times, so the sequence of statements also executes N times.
If we assume the statements are O(1), the total time for the for loop is N*O(1), which is O(N) overall.

Nested loops

for (i=0;i<n;i++) {
  for (j=0;j<n;j++) {
       sequence of statements
   }
}

The outer loop executes n times. Every time the outer loop executes, the inner loop executes m times. As a result, the statements in the inner loop execute a total of n*m times. Thus, the complexity is O(n*m).
In some cases where the stopping condition of the inner loop is j<n instead of j<m, the total complexity for the two loops is O(N2).

for (i=0;i<n;i++) {
  for (j=i+1;j<n;j++) {
     sequence of statements
   }
}

In above example, we can’t multiply the number of iterations of the outer loop times the number of iterations of the inner loop, because the inner loop has a different number of iterations each time.
The number of iterations in a loop can be calculated in following way:

Value of i       Number of iterations of inner loop
    0                  n 
    1                 n-1
    2                 n-2
    -                 ---
   n-2                 2
   n-1                 1

The total number of times the sequence of statements executes is: n+ n-1 + n-2 + … + 3 + 2 + 1. The total is O(N²).