Data Structures and Algorithm:
Organize the data in a way that is easy to handle and perform actions on.
Types of Data Structures:
Introduction to Algorithms: An algorithm consists of instructions to carry out a task or solve a problem (this is a theoretical way of explaining).
Let's consider an algorithm to calculate the sum of 'n' natural numbers.
There are two different ways to write it.
Way 1
public int findSum (int n){
return n*(n+1)/2;
}
Way 2
public int findSum (int n){
Int sum =0;
for(int i = 1; i<=n;i++){
sum = sum +i;
}
return sum;
}
Out of these two, we need to decide which is better based on time and space complexity.
Way 1 is better than Way 2 because the number of iterations is fewer and it requires less space to store the code.
A mathematical model that aids us in determining the Time and Space Complexity is called Asymptotic Analysis of an Algorithm.
Asymptotic Analysis of an Algorithm: assists in assessing the performance of an Algorithm concerning input size and its growth.
Asymptotic Notations aid us in identifying:
Best Case
Average Case
Worst Case
Types of Asymptotic Notations: for performing runtime analysis of an algorithm.
Omega(Ω) Notation
Big O (O) Notation
Theta (θ) Notation
Omega(Ω) Notation: denotes the lower bound of algorithm’s running time.
Big O (O) Notation: denotes the upper bound of algorithm’s running time.
Theta (θ) Notation: denotes both the upper and lower bound of an algorithm’s running time (i.e., average amount of time an algorithm can take to complete).
Big O Notation is the most used notation. Rules to be followed.
If it’s a single processor and performs sequential execution of statements
Assignment, Arithmetical, Logical Operations takes 1 unit of time.
Return statements, other small/ Single operations takes 1 unit of time.
Drop Lower order terms in polymorphic expression and constant multipliers.
To be Continued..