Why You Must Learn Prefix Sum Algorithm? | Need of prefix-sum Algorithm | EP1

Why You Must Learn Prefix Sum Algorithm? | Need of prefix-sum Algorithm | EP1

Articles, Blog , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 4 Comments


Hello my dear friend, Welcome to my youtube
channel. Today, I am going to tell you, why you must
learn the prefix sum Algorithm. Let’s start the same with the help of an example. In this example, I have taken an array A [] of
seven elements, indexed from zero to six. And, If I will ask you a question. Can you calculate the sum between a range
from zero to four? Then, how will you do that?
you probably will add all the numbers from zero to four. If you add six plus three plus minus two plus
four plus minus one. Which is equals to ten? So, answer to this query will be 10. And, If the same thing you will ask your computer
to do it. You will give instruction something similar
to this. Here, you will loop through the element from
zero to four and by adding every element to the sum. Finally, you will return the sum which holds
the result. But what, If I ask another query, that I need sum between the range from two
to six. You will again follow the similar procedure
but this time your loop will run from index two to index six. Let’s generalize this for n size array. suppose, you have n elements in the array
and you have to calculate the sum in a range from zero to n in the worst case. So, you will run a loop up to n times. So, the time complexity of calculating the
sum between range zero to n elements is O(n). Or in general, to calculate the sum between
the range from start to end. You can feed something similar instruction
to the computer. If you have one query, you are going to perform
n operation in the worst case, only one time. If you have two queries, you are going to
perform n operation in the worst case, two times. In the same way, for three queries, you are
going to perform n operation three times. So, for each query, we are going to perform
O(n) operation. But what If you have m number of queries? So, you will have one more outer loop which
will run through from 1 to m. So, the outer loop will execute m times and
the inner loop will execute n times in the worst case. Then the overall time complexity of this
the algorithm would be O(m*n). Let’s analyse this Algorithm. To perform m number of queries on n size array
will take O(mn) time. But an efficient algorithm can do the same
task in O(n) time in the worst case and that algorithm is known as “Prefix Sum Algorithm”. Which we will learn in the next video. So, Key take away from this lesson. A normal algorithm takes O(m*n) time to
perform m number of queries to find the range-sum on n size array. But prefix sum algorithm takes O(n) time
to perform m number of queries to find range sum on n size array. which is the huge improvement over O(m*n) time. I hope it’s clear to you, why you must know
the prefix sum algorithm. and if you still have some doubts, please
let me know in the comment section. please don’t forget to like, comment, share
& subscribe to my youtube channel.

4 thoughts on “Why You Must Learn Prefix Sum Algorithm? | Need of prefix-sum Algorithm | EP1

  • JAVAAID - Coding Interview Preparation Post author

    Hello Coding Lover,

    If you have any doubts , please let me know in comments.

  • Mayur kadam Post author

    Nice one most of the time i used traditional one 😅
    Whenever you upload that video just notify me

  • Akash Post author

    2:59 why there is a outer loop since all queries have different input so to calculate sum for each query we have to run the for loop for each query all the for loop will be execute for n times in worst case for m queries so the complexity will be m*O(n) why it is O(m*n) ?
    Please clarify my doubts.

  • Mohammad Imran Post author

    neeed code attachment plz

Leave a Reply

Your email address will not be published. Required fields are marked *