 # Time and Space Complexities from code

Contents

## Introduction

Finding the Time and Space Complexities from codes of a piece of code is an important step in understanding its performance and optimizing it for efficiency. In this article, we will explore the basic concepts of time and space complexity, and how to determine them from a given piece of code.

## Time Complexity

Time complexity refers to the amount of time it takes for a program to execute, and is typically measured in terms of the number of basic operations the program performs. Common basic operations include mathematical operations, such as addition and multiplication, as well as data access operations, such as array lookups and object property access. The time complexity of a program can be determined by counting the number of basic operations it performs and analyzing how that number relates to the size of the input data.

One common way to measure the time complexity of a program is to use the “big O” notation. This notation expresses the time complexity of a program as an upper bound on the number of basic operations it performs, as the size of the input data increases. For example, a program that performs a linear search of an array has a time complexity of O(n), where n is the size of the array. This means that, as the size of the array increases, the number of basic operations the program performs also increases, but at most linearly.

Let’s start with a simple example. Suppose you are given an array A and an integer x and you have to find if it xexists in array A.

See also  SUM OF THE NATURAL NUMBERS USING RECURSION and FACTORIAL USING RECURSION￼

A simple solution to this problem is to traverse the whole array A and check if any element is equal to x.

``````for i : 1 to length of A
if A[i] is equal to x
return TRUE
return FALSE``````

Let’s consider an example:

``````int count = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < i; j++)
count++;``````

Lets see how many times count++ will run.

When i=0, it will run 0 times.
When i=1, it will run 1 time.
When i=2, it will run 2 times, and so on.

Total number of times the count++ will run is 0+1+2+….(N-1) = (N*(N-1))/2. So the time complexity is O(N^2)

## Space Complexity

Space complexity, on the other hand, refers to the amount of memory a program uses during its execution. Like time complexity, it can be measured in terms of the number of basic operations the program performs, but it also includes the amount of memory used by data structures and variables. For example, a program that creates a new array for each element it processes has a space complexity of O(n^2), where n is the size of the input data. This is because, as the size of the input data increases, the number of arrays created also increases, and so does the amount of memory used by the program.

To determine the time and space complexities of a given piece of code, it is important to analyze each individual operation and data structure used, and understand how they contribute to the overall complexity of the program. For example, a nested loop that performs a linear search inside of an outer loop has a time complexity of O(n^2), because the number of basic operations it performs is proportional to the square of the size of the input data. 