Time Complexity

• This type of complexity represents the time required to execute an algorithm.
• The time complexity of an algorithm is the amount of time it takes for every statement to complete.
• It is highly dependent on the size of the input data size.
• It shows the effectiveness of the algorithm by evaluating its performance in terms of the time required for execution.

Example:

multi ← 1 
i ← 2 
 while i ≤ n do 
     multi ← multi ∗ i 
     i ← i + 1 
 end while

• The Time Complexity of the above multiplication function can be calculated as follows:
  • The time complexity of lines 1 and 2 would be $\mathcal{O}(1)$.
  • Line number 3 shows the while loop.
  • Therefore, lines 4 and 5 repeats (n -1) times.
  • Hence, the time complexity for lines 4 and 5 would be $\mathcal{O}(n)$.
  • Finally, combine all the time complexities of all lines to get the overall time complexity of the multiplication function.
  • Therefore, $\mathbf{T(n) = \mathcal{O}(n)}$.

Space Complexity

• This type of complexity represents the amount of memory used by a program for execution.
• It computes the memory space needed for all the variables, inputs, and outputs.
• It is highly dependent on the temporal values that are stored while running and the auxiliary variable size.
• It shows the effectiveness of the program in terms of how it will save space during execution.

Example:

int sum, i 
 while i ≤ n do 
     sum ← sum + a[i] 
     i ← i + 1 
 end while 
 return sum

• The Space Complexity of the above sum of elements of an array function can be calculated as follows:
  • Space complexity would be the number of allocated bytes and generally integer takes a space of 4 bytes in the memory.
  • Line 1 allocates memory space for two integers therefore, space complexity for line 1 is $4\ bytes \times 2 = 8\ bytes$.
  • Line 2 shows the while loop.
  • Lines 3 and 4, allocates values to an existent variable therefore, memory space is not allocated here.
  • Line 6, returns the statement therefore it will allocate one more memory space as $4\ bytes \times 2 + 4\ bytes = 12\ bytes $.
  • Finally, combine all the space complexities of all lines to get the overall space complexity of the sum of elements of an array function and also consider the array is allocating n cases of integers in the function.
  • Therefore, $\mathbf{S(n) = n + 12 = \mathcal{O} (n)}$.