0

I'm trying to figure out how to fill out this chart, i.e. how many times each line runs. When I do tracing, I know that the inner loop runs i+1 times, but I also don't know how to correlate that to the "Times" section in the following chart.

                                           Cost      Times
void foo( Array A, int n) {
1.     for(int i = 1 ; i <= n ; i*=2)      c1         ?
2.        for(int j = n ; j > n-i ; j--)   c2         ?
3.            cout << A[j] << endl;        c3         ?

My tracing when n = 10:

+-----+----+-----------+-----------------+
|  i  | j  |  j > n-i  | Total run times |
+-----+----+-----------+-----------------+
| 1   | 10 | 10 > 10-1 |                 |
|     |  9 | 9 > 9     | 2               |
| 2   | 10 | 10 > 10-2 |                 |
|     |  9 | 9 > 8     |                 |
|     |  8 | 8 > 8     | 3               |
| 4   | 10 | 10 > 10-4 |                 |
|     |  9 | 9 > 6     |                 |
|     |  8 | 8 > 6     |                 |
|     |  7 | 7 > 6     |                 |
|     |  6 | 6 > 6     | 5               |
| ... |    |           | i+1             |
+-----+----+-----------+-----------------+
Machavity
  • 30,841
  • 27
  • 92
  • 100
EthanSmith23
  • 9
  • 3
  • 1
    While I agree that this is not an identical duplicate, the process described in the duplicate still applies. Apply the process and you'll get your answer. – user4581301 Sep 02 '20 at 17:48
  • 1
    @JanSchultke That's not what an edit should be. You can leave such as a comment. Also, the calculation principle stays the same more or less. – πάντα ῥεῖ Sep 02 '20 at 17:48
  • I have read the duplicate answer and it by no means fully answers the question. From that answer, I still have no idea how to do the same process for this loop, where we seemingly have `O(log n * n)` complexity (perhaps?) The edit was necessary because it seemed like you have closed the question because you didn't spot the `i *= 2` detail. And I am sure it won't be reopened when other people miss that detail too. I disagree that the calculation principle stays more or less the same. That remains to be proven. – Jan Schultke Sep 02 '20 at 17:53
  • 1
    Jan, it is a simple nested loop. If we had a different question and answer for trivial differences in mathematics we'd have different questions for "What is 1+1?" and "What is 1+2?" That way lies madness. Whoever wrote this assignment laid it out pretty well. The learner should get the multiplicative nature by figing out C1, C2, and C3. – user4581301 Sep 02 '20 at 17:56
  • 1
    Note: The inner loop isn't O(n). The `n-i` in the exit condition should be the tricky part, not the `i *= 2`. – user4581301 Sep 02 '20 at 18:00
  • @user4581301 all the answers in the duped question relate to `O(n*n)` complexity loops, which are easy enough to spot. This loop falls into a completely different complexity class. It would be executed `1 + 2 + 4 + 8 + ... n` times which is approximately `n * 2 - 1`, assuming that `n` is a power of 2. So surprisingly, it's O(n) complexity despite being a nested loop. I would say these problems are different enough to not warrant being called duplicates. – Jan Schultke Sep 02 '20 at 18:01
  • 1
    We disagree. That happens. @πάνταῥεῖ 's point about the edit still stands. Plead your case in the comments, not in the question. – user4581301 Sep 02 '20 at 18:02
  • @user4581301 I agree that if I was just pleading my case, it would be absolutely inappropriate for me to edit this question as I did. However, I myself thought that the question is a duplicate until I spotted the `i *= 2` loop step. I felt that bringing attention to this technical detail should be part of the question, as it is not merely my opinion. – Jan Schultke Sep 02 '20 at 18:05
  • @JanSchultke As mentioned that's the job of the OP to edit, not yours. Leave a comment instead. – πάντα ῥεῖ Sep 02 '20 at 18:13
  • 1
    @JanSchultke Please don't edit commentary into the question. That's what comments are for. If there is any deeper issue here, please take it to Meta. Thanks. – Machavity Sep 02 '20 at 21:24

0 Answers0