-1

The screenshot of the question

My calculation is:

 statement              | time 
------------------------|--------
var value = 0;          | 1
for(var i=0;i<n;i++)    | 1 + (n+1) + n 
for(var j=0;j<i;j++);   | n + n*(n(n+1)/2 +1) + n* n(n+1)/2
value += 1;             | n*(n(n+1)/2
Nick
  • 1
  • 2
  • is that semi-colon after second loop intensionally put ?? – Papai from BEKOAIL Sep 11 '20 at 11:00
  • It's not in the image, so probably not – tobias_k Sep 11 '20 at 11:01
  • 1
    `j` runs from 0 to `i - 1`. That makes `i` iterations. Hence the total number of iterations is the sum `0 + 1 + 2 + ... + (n - 1) = n(n - 1)/2` – Ronald Sep 11 '20 at 11:02
  • Is the question about total number of statements being evaluated (including e.g. the comparison and increment in the loops), or how often the `value += 1` line is executed (and hence what's the final value of `value`)? – tobias_k Sep 11 '20 at 11:05
  • @Ronald Your comment is the answer. Please consider converting it to an answer by enlarging on the topic and using a technical answer. – Codor Sep 11 '20 at 11:06

3 Answers3

0

Let's take the initial few iteration counts and see.

i (counter)           j (# of iterations for each value of i)
0th                   0
1st                   1
2nd                   2
.                     .
.                     .
(n-1)th               n-1

Now the sum of first N integers is defined as n(n+1)/2 where the range starts from 1 and goes till n. More details here.

In our case, range starts from 0 and goes till n-1 (RHS in the above table). Replacing n with n-1 in the summation formula, you get n(n-1)/2.

Siddharth Kamaria
  • 2,448
  • 2
  • 17
  • 37
  • 1
    A detailed explanation on the formmula can be found [here](https://brilliant.org/wiki/sum-of-n-n2-or-n3/) – Codor Sep 11 '20 at 11:09
0

The Big O complexity is O(n*n), so n squared.

The number of operations is n(n-1)/2.

The Big O complexity ignores constants and lower order terms.

Matei Florescu
  • 1,155
  • 11
  • 23
0

The question is poorly formulated and thus has no precise answer. Indeed, the author did not say which operation "counts". For example, when i=0, the inner loop is executed once (at least initialization and test), while its body is not.

Now if we only count the number of incrementations of value, the innermost loop performs exactly i of them, and the outer loop makes i vary from 0 to n-1. Hence a total of Tn-1 = n(n-1)/2 (triangular number).

  • I think it means the upper bound time complexity, which is the inner loop. – Nick Sep 12 '20 at 01:37
  • @NicholasC.: that does not better the question, and the upper bound is certainly not "the inner loop". –  Sep 12 '20 at 04:58