What Is Time Complexity And Space Complexity Algorithm With Example

March 12, 2021February 21, 2022 CS Electrical And Electronics

Hello guys, welcome back to my blog. In this article, I will discuss what is time complexity, what is space complexity, an example of time complexity and space complexity, etc.

If you have any doubts related to electrical, electronics, and computer science, then ask questions. You can also catch me on Instagram – Chetan Shidling.

Also, read:

Time Complexity And Space Complexity

Suppose Z is an algorithm and N be the size of the data in the input, space and time used by algorithm Z are the two main factors that decide the efficiency of Z. Time factor is determined by counting the number of key operations such as comparisons in the sorting algorithm. Space factor is determined by counting the maximum space of memory required by the algorithm.

The complexity of an algorithm f(n) gives the running time or/and the storage needed by the algorithm in terms of N as the size of data in the input.

Space Complexity

The space complexity of an algorithm describes the quantity of memory space needed by the algorithm in its life cycle. The space needed by an algorithm is equal to the sum of the following two elements.

A fixed part is a space needed to store certain data and variables, which are independent of the size of the problem. For example, constants used and simple variables, program size, etc.

A variable part is a space needed by variables whose size depends on the size of the problem. For example, dynamic memory allocation, recursion stack space, etc.

Space complexity S(P) of any algorithm P is S(P) = C + SP(l), where C is the part that is fixed and S(l) is the part that is variable of the algorithm, that depends on instance characteristics l.

Following is a good example that tries to tell the complexity concept.

Example:

Algorithm: SUM(A, B)
Step 1 - START
Step 2 - C <- A + B + 10
Step 3 - Stop

Here we have the three variables A, B, & C, and one constant. Hence S(P) = 1 + 3. Now, space depends on data types of given variables and constant types and it will be multiplied accordingly.

Time Complexity

The time complexity of an algorithm represents the quantity of time needed by the algorithm to run to completion. Time requirements can be defined as a numerical function T(n), where T(n) can be measured as the number of steps, provided each step consumes constant time.

For example, the addition of two n-bit integers takes n steps. Consequently, the total computational time is T(n) = c*n, where c is the time taken for the addition of two bits. Here, we observe that T(n) grows linearly as the input size increases.

Well, guys, this was about Time Complexity And Space Complexity. I hope this article “Time Complexity And Space Complexity” may help you all a lot. Thank you for reading.

Also, read: