Why do care about the complexity of a program (using dart)?

Let us understand with an example of a program which checks whether our input is prime or not. For this let we take two different approaches or algorithms

First Approach: brute force

Let’s say we simply write a program, without keeping complexity in mind. And then understand the time complexity of below program.

For i=2 to n-1.If i divide n, n is not prime

The complexity of this algorithm is O(n)

For the worst case, the loop will run n-2 times. For,

n=101 it takes 99 ms

n= 10¹⁰ it takes 115 days

Second algorithm

Here we have changed the above program to have the complexity of O(√n).

For i=2 to √n.If i divide n, n is not prime

The complexity of this algorithm is O(√n)

For worst case loop will run √n-1 times. For,

n=101 it takes approx 9 ms

n= 10¹⁰ it takes 1.66 min

From the above discussion, we can see how decreasing the complexity from n to √n changes the run time. For small inputs, it is time difference is small but for large inputs, it is very large as it is increasing exponentially.

Furthermore, we will better understand by graph between the complexity variables of above algorithm….

As we can see from the above graph for the small input the difference between the curve is less. But as we increase the value of our input the corresponding difference between the curve is increased with a large difference.

Due to all the above reasons, we need to measure the complexity of an algorithm and compare the best one for large inputs. We deal with large inputs when comparing the complexity because for small inputs there is no much difference in time and space at all, we can neglect the difference as it is too small. But we must do for the large inputs, we can’t neglect them as they may lead to change the whole performance of our algorithm