First time here? Checkout the FAQ!
x
+2 votes
5.3k views
asked in Data Structures and Algorithms by (360 points)  

Assume we have the following algorithm:

How should I count the number of each operation?

  

1 Answer

+2 votes
answered by (115k points)  
selected by
 
Best answer

For $n<10$ the answer is obvious because the program stops at "return 0;". for $n \ge 10$, please start with $n=10$ and run the algorithm by yourself and count how many times it will occur. The Python implementation is as follows. In the following code, you can see the lines that should be counted have labels of $c1, c2, c3, c4, c5, c6$ . You can see and execute the full program here.

n = 10
s= 0
count = 0
i = 0
while(True):  #c1
  for i in range(5, count+1): #c2
    s = s+i #c3
  if (count > n): #c4
    break #c5
  count = count + 1 #c6
print(s)

If you run the algorithm by yourself on paper, you will have the following table. In this table, we start for $n=10$, and under each label such a $c1$ we have written if the line is executed, and the number in front of x is the number of execution. For example, for $c3$, when $count=9$ in the row, we have"x 5" which means $s=s+i$ executed 5 times (look at for condition: for i = 5 to count , and count is 9, so the body of for loop,$s=s+i$ ,will be executed 5 times).

In the total row, we counted how many times in total for $n=10$ the lines are executed and tried to draw a general conclusion, based on $n$. For example for $c1$, and for $n=10$ we counted $12$ execution, so it is probably $n+2$ in a general situation (you can prove it using induction). For $c3$, it will be summations of numbers from $1$ to $n-3$, as we see in the case of $n=10$ it will be $1+2+3+4+5+6+7=\frac{7\times8}{2}$, because we have $1+2+3+...+(n-1)+n = \frac{n(n+1)}{2}$. Therefore, for any n, it seems for $c3$ we should calculate the sum of natural numbers until $n-3$ (as for 10 we sum up up to 7). If you replace $n-3$ in the equation, you will have $1+2+3+....+(n-4)+(n-3) = \frac{(n-3)(n-2)}{2}$

 

n count c1 c2   c3 c4   c5 c6
10 0 x 1 x 1   x 1   x 1
  1 x 1 x 1   x 1   x 1
  2 x 1 x 1   x 1   x 1
  3 x 1 x 1   x 1   x 1
  4 x 1 x 1   x 1   x 1
  5 x 1 x 1   x 1 x 1   x 1
  6 x 1 x 1   x 2 x 1   x 1
  7 x 1 x 1   x 3 x 1   x 1
  8 x 1 x 1   x 4 x 1   x 1
  9 x 1 x 1   x 5 x 1   x 1
  10 x 1 x 1   x 6 x 1   x 1
  11 x 1 x 1   x 7 x 1   x 1  
               
Total:   $12$ $12$  $1+2+…+6+7 = \frac{7\times8}{2}=28$ $12$   $1$ $11$
    $n+2$ $n+2$  $1+2+...+(n-4)+(n-3) = \frac{(n-3)(n-2)}{2}$ $n+2$   $1$  $n+1$
...