Big O notation

What is meant by Algorithm Analysis?

Algorithm analysis refers to analysing and understanding the performance characteristics of algorithms. It involves studying how algorithms perform in terms of space and time as the size of input grows. Analysis of an algorithm can help us decide what algorithm can we choose to solve a particular problem.

Developers usually consider the analysis of algorithms for factors such as time behaviour, space utilization, scalability and possible optimization strategies.

Why Analysis of Algorithms is important?

Predicting Algorithm Behavior: Algorithm analysis provides a way to estimate how an algorithm will perform in terms of time and space requirements without actually implementing it on a specific computer or system.
Approximation and Imperfection: Algorithm analysis offers a theoretical upper or lower bound on how an algorithm will perform as the input size grows.
Algorithm Comparison: One of the primary purposes of algorithm analysis is to compare different algorithms and determine which one is most suitable for a specific task. Thereby we can then change our approach as to what algo can be considered by trading off between space or time.

Asymptomatic analysis

In asymptomatic analysis, we analyse an algorithm based on input size. For example, when we want to find an element in an array that is sorted, the time complexity may vary linearly.

Say when an element is at the start of the array we iterate only once, but what if the element is not there at the last, We have to iterate the entire array and return, so the worst-case time complexity in this case is O(n), where n is the size of the array.

Now we apply binary search to find an element in an array it would take log(n) time which is far more optimised and better in terms of usability.

Similarly, if we have to calculate factors of a number. One approach would be to approach from 1 to number, and then check for each number. The time complexity in such a case would be O(n).

For example, we know that factors of 24 are 1,2,3,4,6,8,12. If we consider the first approach we will have to start from 1 and then check for each number till 24.

for(int i=0;i<n;i++)
{
if(n%i==0)
{
system.out.print(i);
}
}

To optimise this, we know that factors occur in pairs i.e. 1 and 24, 2 and 12, 3 and 8, 4 and 6. So we can iterate till the root of the number and find the pairs.

for(int i=0;i*i<=n;i++)
{
if(i!=n/i)
{
System.out.println(i+" "+n/i);
}
else
{
System.out.println(i);
}
}

Input Size	Approach one	Approach two
10	0ms	0ms
10^8	1 sec	10^(-4) sec
10^10	100 sec	10^(-3) sec
10^18	316 years	~ 10 sec

Now we see that a small observation in the approach can make a whole lot of difference in the time complexity of the code.

Big O notation:-

The "O" stands for "order of" and is used to describe an upper bound. It indicates the worst-case scenario for an algorithm's performance.

Some common Big O notations and their corresponding growth rates are:

O(1) (constant time)
O(log n) (logarithmic time)
O(n) (linear time)
O(n log n) (linearithmic time)
O(n^2) (quadratic time)
O(2^n) (exponential time)
O(n!) (factorial time)

When analyzing algorithms using Big O notation, we focus on the term with the highest power and ignore the rest of the terms.

Real-World Applications- Optimizing software for user experience and scalability

Time complexity has a significant impact on real-world applications, especially in terms of user experience and scalability. Let's explore how time complexity affects various aspects of software development and optimization.