0
$\begingroup$

In my class my teacher calculated the time complexity for this algorithm, relative to the number of sum operations executed:

enter image description here

She represented the cost of the algorithm by the following sum:

$\sum\limits_{i=1}^n \sum\limits_{j=1}^i\sum\limits_{k=1}^j 3 = \frac{n^3}{2} + \frac{3n^2}{2} + n $

The step by step used to solve the sum bellow: enter image description here

n = 10
count=0
for i in range (0, n):
    for j in range (0, i):
        for k in range (0, j):
            count+=3

print count

Then, I wrote a algorithm in python to verify the solution, but it not produce the expected output, for example, for n = 10 we expected 660 operations, but it print 360.

Change the index to start with 1 like in the bellow didn't worked either, in fact it got more distance from the expected (252).

n = 10
count=0
for i in range (1, n):
    for j in range (1, i):
        for k in range (1, j):
            count+=3

print count
$\endgroup$
  • $\begingroup$ You cannot expect 860 operations, as 860 is not divisible by 3. Running loops as intended gives $count = 858$. $\endgroup$ – Evil Apr 24 '16 at 0:49
  • $\begingroup$ @EvilJS Sorry, the 860 is a typo it should be 660. Where did you find the 858 ? $\endgroup$ – Guilherme Torres Castro Apr 24 '16 at 1:05
  • $\begingroup$ Very easy, I just executed your triple loop and got result - it was before the edit. From 0 to n inclusively. And without the last element it was 360. Now when you changed the code, if you do $count += 3$ it is not the same as sum of $i, j, k$ indices on every iteration. Please look at D.W. answer and comment, if you got result somehow, but describe it differently in pseudocode, differently in python and MathJax it is the most probable place of error. $\endgroup$ – Evil Apr 24 '16 at 1:59
  • $\begingroup$ @EvilJS My mistake, the only operation we should count is the sum in the most deep loop. Even so you are able produce 858 as output, or did you count the for operations ? Perdon my ignorance, but can you elabore a little more how you got the 858 ? $\endgroup$ – Guilherme Torres Castro Apr 24 '16 at 2:17
  • 1
    $\begingroup$ I'm going to repeat my comment. How exactly did you get 360? You said you wrote an algorithm in Python, but you don't show us the Python; one possible error is that you wrote the Python wrong. How have you ruled that out? Note that your pseudocode at the top of the question does not match the Python at the bottom. $\endgroup$ – D.W. Apr 24 '16 at 2:24
1
$\begingroup$

Now, you need to make index reach n, rather than go just up to it,
so instead of range(1,n), it should be range(1,m) for some m such that ​ n < m .
To avoid n+1, one also needs ​ m ≤ n+1 . ​ ​ ​ Combining those gives ​ n < m ≤ n+1 .
The simplest such m is obviously ​ m = n+1 , ​ so your initial range should be range(1,n+1).

$\endgroup$
4
$\begingroup$

In Python, range(0,n) iterates through the values 0, 1, 2, .., n-1 (but not n). Therefore, your summation should have been

$$\sum_{i=0}^{n-1} \cdots$$

rather than

$$\sum_{i=1}^{n} \cdots$$

and similarly for the other sums as well.

$\endgroup$
  • $\begingroup$ 0 to n-1 and 1 to n are not equivalent? Anyway change the ranges to 1 to n-1 did not work either. $\endgroup$ – Guilherme Torres Castro Apr 24 '16 at 0:59
  • $\begingroup$ Just to clarify the original program is not written is python is a PseudoCode with i <- 1 to n do. What's bother me is even if a change the program range (1 to n) it will no produce the expected output. $\endgroup$ – Guilherme Torres Castro Apr 24 '16 at 1:01
  • 1
    $\begingroup$ @GuilhermeTorresCastro, rather than posting comments, I suspect you need to edit your question. I can only go by what's in the question; I can't read your mind. Your question says "Looking at this algorithm write in python".... If you say it's in Python, we'll take you at your word. If it's not written in Python, you need to edit the post to define your notation (e.g., what you mean by range), and tell us exactly how you measured how many operations were performed (not the calculations; but how did you run the algorithm and get 360?). $\endgroup$ – D.W. Apr 24 '16 at 1:40
  • $\begingroup$ Ok, thanks for you suggestion I update the question with the real problem. $\endgroup$ – Guilherme Torres Castro Apr 24 '16 at 1:56
0
$\begingroup$

Your teacher was incorrect in thinking that a triple summation of i + j + k (in Python, temp += i + j + k) equals a triple of summation of 1 + 1 + 1 (in Python, temp += 1 + 1 + 1 or temp += 3). See my step-by-step work attached at bottom.

The triple summation of 1 + 1 + 1, i.e. incrementing by 3, over k from 1 to j, j from 1 to i, and i from 1 to n, equals (n3 + 3*n2 + 2*n) / 2. For n = 10, for instance, 1320/2 = 660. Simple Python 3 code confirms this math.

In Python 3, n = 10 count=0 for i in range (1, n+1): for j in range (1, i+1): for k in range (1, j+1): count+=3 print(count) 660

The more intricate summation of (i + j + k) over k from 1 to j, j from 1 to i, and i from 1 to n, equals (n4 + 4*n3 + 5*n**2 + 2*n) / 4, which is exactly (n+1)/2 times the previous sum. Can you deduce why? Because, on average, the quantities i, j, and k will be halfway between 1 and n. For n = 10, for instance, 14520/4 = 3630. Again, Python 3 code that increments count += i + j + k confirms this result at n = 10.

n = 10 count=0 for i in range (1, n+1): for j in range (1, i+1): for k in range (1, j+1): count+= i + j + k print(count) 3630

Triple summation of i + j + k

$\endgroup$
  • $\begingroup$ Please refrain from posting mathematical formulae as images (and especially in wrong orientation). This site provides full LaTeX support. $\endgroup$ – dkaeae Jan 3 at 15:57
0
$\begingroup$

Your implementation does not match the algorithm written in the pseudo-code. In the pseudo-code: for i ← 1 to n do means i could take n values from 1 to n. for simple, let's consider the last iteration, namely i=n. Then consider the second loop: for j ← 1 to j do could be reduced to: for j ← 1 to n do That's to say, j could also take n values from 1 to n. But for your implementation in python, for i in range (0, n) i could take n values from 0 to n-1. Let's also consider the last iteration, namely i=n-1. Unfortunately, for the second loop: for j in range (0, n-1) here j can only take n-1 values from 0 to n-2. Obviously mismatched to the original algorithm. Two ways to solve your problem:

Index start from 1 and use LCRC rule:
for i in range (1, n+1): for j in range (1, i+1): for k in range (1, j+1): count+=3 or start from index 0, but use LCRC rule for all inner loops:
for i in range (0, n): for j in range (0, i+1): for k in range (0, j+1): count+=3 The first one is preferred as it exactly match the algorithm. But the second one could let you clearly understand the difference between the outer loop and inner loops.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.