# 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.

JAVAAID - Coding Interview PreparationPost authorHello Coding Lover,

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

Mayur kadamPost authorNice one most of the time i used traditional one ðŸ˜…

Whenever you upload that video just notify me

AkashPost author2: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 ImranPost authorneeed code attachment plz