Time and Space Complexity
Time Complexity

• This is the amount of time taken by an algorithm to run as a function of the length of the input Time complexity has 2 parts these are: -Fixed part: 1 unit of time (constant time) -Moving part: n unit of time (constant time * number of repetitions) Each operation is considered to take 1 unit of time to calculate overall time complexity basically you add up all the statements. Each statement might have 1 or more unit of time.

Lets Use the example Below

Let's assume that

1 operation = 1 unit of time

// FIXED PART
function sum(a, b) {
return a + b; // one statement with one operation (1 unit of time)
}

// Overall Time complexity of sum function
T(n) = 1 unit of time

// MOVING PART
function sumOfN(n) {
let sum = 0; // 1-statement, 1-operation = 1 unit of time

// 1 loop statement repeates for n times
// any operations that falls in this loop is repeated n times
for(let i=0; i < n; i++) { 
    sum += i; // 1 operation * n
}

return sum; // 1-statement 1-operation (print)

}

// Overall Time compexity for sumOfN function is
T(n) = 1 unit of time + n unit of time + 1 unit of time

Space Complexity

• Space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input.``

- Space complexity is basically sum of:
-fixed part: space required for storing data which is not dependent of input size.
-variable part: space that is calculated based on input size.

In this post, you will learn what asymptotic notations are. Also, you will learn about Big-O notation, Theta notation and Omega notation.

Equation can be defined as below

Space complexity of an algorithm n can be

S(n) = Fixed Part + Variable Part

To calculate space complexity of an algorithm you have to assign 1 unit of space to operations where it requires a memory. For example: creating a new variable require some space let say it is 1 unit of space.

We are not going to learn in depth about how to exactly calculate space required by a program rather we would learn about how many unit of space does a program require to solve a specific problem.

`
// FIXED PART: constant space (1 unit of space)
var a = 1; // variable assignment = 1 unit of space

// MOVING PART: an operation is repeated based on input size of n
for (var i=0; i<n; i++) { // this statement will repeat for n times
var z = i; // 1 unit of space * n
}
`
In above example, we have fixed part and moving part. You need to understand fix part is basically constant space i.e. 1 unit of space. Moving part is quite different, they are usually dependent of input size in our case its n.

When an operation is repeated n times that means all the operations that falls under this statement they also repeated n times. In our case a for loop repeats n times therefore variable z which has 1 unit of space is repeated n times.

To calculate overall space complexity of above code:

Equation: S(n) = Fixed Part + Moving Part

S(n) = 1 unit of space + n unit of space

Asymptotic Notations
These are the mathematical notations used to describe the running time of an algorithm when the input tends towards a particular value or a limiting value.

There are mainly three asymptotic notations:

• Big-O notation

• Omega notation

• Theta notation

Big-O Notation (O-notation)

Big-O notation represents the upper bound of the running time of an algorithm. Thus, it gives the worst-case complexity of an algorithm.

Theta Notation (Θ-notation)

Theta notation encloses the function from above and below. Since it represents the upper and the lower bound of the running time of an algorithm, it is used for analyzing the average-case complexity of an algorithm.

Omega Notation (Ω-notation)
Omega notation represents the lower bound of the running time of an algorithm. Thus, it provides the best case complexity of an algorithm.

Writing equations for time/space complexity

Now that we learned about how to calculate space and time complexity its time to learn about how we can write equations for an algorithm. Writing equations would help you clearly understand the time/space complexity of the program.

Later on we will use these equations to find Big O complexities. Let's take one example: you are designing an algorithm to sum of n numbers.

calculate time/space complexity of following function

function sumOfN(n) {
let sum = 0;
for(let i=0; i < n; i++) {
sum += i;
}
return sum;
}

caculate time complexity of above program

time complexity of an algorithm n is

T(n) = sum of all unit time per statement

Let x is equals to 1 unit of time

function sumOfN(n) {
let sum = 0; // x

for(let i=0; i < n; i++) { // n repetition
    sum += i; // x*n
}

return sum; // x

}

T(n) = x + xn + x
= 2x + xn
= 2 + n (because x = 1 unit of time)

caculate space complexity of above program

space complexity of an algorithm n is

S(n) = sum of all unit space per statement

Let x is equals to 1 unit of space

function sumOfN(n) {
let sum = 0; // x

for(let i=0; i < n; i++) { // n repetition
    sum += i; // x*n
}

return sum; // x

}

S(n) = x + xn + x
= 2x + xn
= 2 + n (because x = 1 unit of space)

Finally lets learn different types of BIG O complexities

Followings are some of the different types of time/space complexities:

Constant Time: O(1)
Logarithmic Time: O(log n)
Linear Time: O(n)
Linearithmic Time: O(n log n)
Quadric Time: O(n^2)
Cubic TIme: O(n^3)
Plynomial TIme: O(n^k)
Exponential Time: O(b^n)
Factorial Time: O(n!)

That was what I learnt During the week. See you next lesson for more.