Time & Space complexity

Time complexity

Time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm.

In simple words we can say that it tells how much time our program is taking to run.

Calculating time complexity:-

int i=0;

Here i variable is taking constant time. It is denoted as Big O or O(1).

for (int i = 0; i < n; ++i) {
    System.out.println(i);
}

In above for loop variable n will iterate through n times.

So Time complexity will be o(n).

Different Types of time complexity

1. Worst case time complexity:- Maximum number of times program is taking to complete whole process.
2. Average case time complexity:- The average number of time algorithm is taking to complete the program.
3. Best case time complexity:- The fastest number of times an algorithm takes to complete.

Space complexity

Space complexity is the amount of memory taken by our program to solve a particular task. A good programmer always focus on reducing space complexity.

public static int fibonacci(n) {
    int x = 0, y = 1, z;
    if (n === 0) {
        return x;
    }
    if (n === 1) {
        return y;
    }
    for (int i = 2; i <= n; ++i) {
        z = x + y;
        x = y;
        y = z;
    }
    return z;
}

Here we are using a fixed space for 4 variables. Hence the space complexity is O(1).

Calculating Space Complexity:-

List<Integer> list=new ArrayList<>();
for (int i = 0; i < n; ++i) {
    list.add(i);
}

Here the array-list list will take n space.
Space Complexity: O(n)

Examples of complexity function:-

1. O(n²): if we iterate over more than one loop iteratively then this complexity will occur.
2. O(n): if we simply iterate in one loop.
3. O(log n): if we divide whole array into 2 parts and do search operation then our number of search will become less then this complexity occurs.
4. O(1): if we traverse directly through index then this complexity occurs.

Conclusion

Similar to time complexity space complexity also plays a major role. We can wait for program to complete it’s execution but we can’t increase memory at run time so space complexity is more important.