3 replies to this topic

[ahmed]

Can anyone explain in "easy wordings" on how to count operations taken by an algorithm ?
for example if i have an algo

sum = 0
 for i=1
 to N do
     for j=1 to i do
        sum = sum + i
     end
end

line 1 , performs just a single constant operation(1)
line 2 , the loop it will run (n+1) (not sure ) but i am confused , 5th line will also run (n times)
but i don't get how to actually calculate and make a one formula for all that?I have seen some material but i failed to understand how it's done and it's not clearly shown :(

[WingedPanther]

I'm reformatting your code so it's easier to read/reference

sum = 0
 for i=1 to N do
  for j=1 to i do
           sum = sum + i
      end
end

Line 1: executes 1 time
Line 2: executes the following BLOCK OF CODE N times
Line 3: (which is part of the block being executed N times) executes it's block of code i times each time it is called.

Something important to realize is that i changes each time you hit Line 3. The first time, i = 1. The second, i = 2, etc until i=N. So 2 and 3 combined execute line 4: 1+2+3+4+...+N times.
1+2+3+...+N = N(N+1)/2, and then add the original count on line 1 to finish.

Note: the reason this stuff isn't shown clearly is that it varies heavily with the details of the code. With very minor changes, the above code performance can be changed radically. You have to understand what the code does. There are no simple formulas for it.

[ahmed]

I do understand the code , but the problem is how to write it as a sum up equation

[WingedPanther]

I just showed you.