Understanding of Asymptotic Notation

-
Whenever we solve any problem there is a sequence of steps that needs to be followed. We have already read the term algorithm, which is nothing but a sequence of steps to achieve the result. Our algorithm took some time and space to solve it.
The running time depends upon several factors:-
  • Single/Multiple processor system.
  • R/W speed to memory.
  • CPU speed.
  • 32/64 bit system.
  • Input Size.
Do we really need all the factors to calculate the time complexity? Don't you think the hardware couldn't be a factor in the time calculation of the algorithm? Let's understand this in more detail.
For example, Kavya and I are working on the problem that needs us to calculate the sum of n natural numbers. We come up with a different-2 approach to solve the problem. Now, Kavya has an i7 machine and running the code, it takes less than 1 ms and I have a dual-core machine that takes 5ms and there is a huge possibility that when I run the same code in a high configuration machine then it might take up less time than Kavya's algorithm.
We don't need to bother about all these hardware-related factors in the time analysis algorithm. We consider only the input size along with how our program will behave with respect to the rate of growth in input?
To calculate the time complexity we use asymptotic notation which is a mathematical way of representation. Asymptotic notation is not perfect but it is the best way to analyze the time complexity of the algorithm. With the help of the asymptotic notation, we can easily find out which algorithm is better.
There are three cases to analyze the algorithm using asymptotic notation.
  • O - "Big-Oh" notation
  • Ω - "Big-Omega" notation
  • Θ - "Big-Theta" notation
We will be discussing all the cases in more detail in the upcoming blogs. This would be a solution to the aforementioned problem in this blog with step by step calculation.
Supposedly we have to sum the first n natural numbers then what would our approach be?

Approach 1:-

    public int sum(int n) {
        int sum = 0; // O(1) constant time
        for (int i = 1; i <= n; i++) { // O(n+1) +1 is for termination the loop
            sum+=i; // O(n) adding value of current i to previous calucate sum
        }
        return sum; // O(1) returning the value 
    }

Approach 2:-

    public int sum(int n) {
        return n* (n+1)/2; // O(1) constant time.
    }
We can easily guess the time complexity of approach 1 is O(n) linear time and approach 2 is O(1) constant time. We will see the rules of the time complexity calculation.
Location: Delhi, India

Comments

Post a Comment

Popular posts from this blog

Recursion

-
Image
The process in which a function calls itself and only works where we call the same operation multiple times with different inputs. In every call, we try to make the problem smaller. There must be a base case where the system will stop the recursion and give you a result back. It internally stores the recursion state in the method call stack. If there is no base condition in the recursion method then it will go into an infinite loop and you might face the StackOverflow Exception . There are several types of recursion:- Head Recursion Tail Recursion Tree Recursion Nested Recursion Head Recursion It will call recursively first then at the end do all the computation. private static int factorial( int number) { return (number== 1 )? number : number* factorial (number- 1 ) ; } factorial(5) (5* factorial(5-1)) (5* (4* factorial(4-1)) (5* (4* (3*factorial(3-1))) (5* (4* (3* (2*factorial(2-1)))) (5* (4* (3* (2* (1*1))))) output = 120 Tail Recur...
Read more

Stack

-
Image
The Stack  looks more like a container which holds the element, will insert element from the top and remove from the top only. It follows the Last in First out(LIFO)  or First In Last out (FILO)  approach. Java uses the method stack area to hold the state of the method if some method calls another method inside it.   public class Demo { public static void main(String[] args) { new Demo().firstCall(); System. out .println( "Main" ); } public void firstCall() { secondCall(); System. out .println( "First" ); } private void secondCall() { thirdCall(); System. out .println( "Second" ); } private void thirdCall() { System. out .println( "Third" ); } } This is how it maintains the method call in the method stack area. It will remove from the top every time and complete its method execution and remove next's top from the stack. This process will continue until th...
Read more

Data Structure & Algorithm

-
Image
I am going to start the complete data structure and algorithm blog series to help the developer community understand the basics and help them become more productive in their work environment. As we all are under lockdown until the next update from the government, I have decided to support my friends and colleague to understand the data structure and algorithm. Let's begin by separating the data structure and algorithm in two terms. When you hear about data structure,  what comes first to your mind. I believe most of you thought of storing any form of data in an efficient way. Yes, You are correct 👍. Now, Second and the most important term is an algorithm , It is a set of rules to be followed to solve a problem. To gain more understanding of the data structure and algorithm, let us take an example:- E.g., We are all going to attend the google conference and they have a single registration desk. If we all reach the registration counter together, to register ourselves. Such a ...
Read more