1

The computational cost will only consider how many times c = c+1; is executed.

I want to represent the Big O notation to use n.

count = 0; index = 0; c = 0;
while (index <= n) {
   count = count + 1;
   index = index + count;
   c = c + 1;
}

I think if the "iteration of count" is k and "iteration of index" is n, then k(k+1)/2 = n.

So, I think O(root(n)) is the answer.

Is that right solution about this question?

user438383
  • 5,716
  • 8
  • 28
  • 43
Druwa
  • 50
  • 5
  • 2
    Try running your code with various values of `n`. Then see what the relationship between those `n` values and the resulting `c` values is. That will be your complexity. – Adrian Mole Apr 23 '22 at 08:48
  • 1
    Yes, your question is more correct than the comments or answers. O(sqrt(n)) is correct for the reasons you give. – Paul Hankin Apr 23 '22 at 09:14
  • Oh, I see. thank you for your comment. – Druwa Apr 23 '22 at 12:10

2 Answers2

0

Let's first see how index changes for each loop iteration:

index = 0 + 1 = 1
index = 0 + 1 + 2 = 3
index = 0 + 1 + 2 + 3 = 6
...
index = 0 + 1 + ... + i-1 + i = O(i^2)

Then we need to figure out how many times the loop runs, which is equivalent of isolating i in the equation:

i^2 = n =>
i = sqrt(n)

So your algorithm runs in O(sqrt(n)) which also can be written as O(n^0.5).

Allan Wind
  • 23,068
  • 5
  • 28
  • 38
  • In the expression `floor(0.5) i^2` the first term `floor(0.5)` equals zero, Are you sure you've put parentheses correctly? – CiaPan Apr 25 '22 at 07:49
  • @CiaPan Thanks! Brainfart on my part. Fxed by omitting it as it wasn't particular important. What I meant was `floor(i/2) * i`. – Allan Wind Apr 25 '22 at 08:32
0

Is that right solution about this question?

This is easy to test. The value of c when your while loop has finished will be the number of times the loop has run (and, thus, the number of times the c = c + 1; statement is executed). So, let us examine the values of c, for various n, and see how they differ from the posited O(√n) complexity:

#include <stdio.h>
#include <math.h>

int main()
{
    printf("    c   root(n)  ratio\n"); // rubric
    for (int i = 1; i < 10; ++i) {
        int n = 10000000 * i;
        int count = 0;
        int index = 0;
        int c = 0;
        while (index < n) {
            count = count + 1;
            index = index + count;
            c = c + 1;
        }
        double d = sqrt(n);
        printf("%5d  %8.3lf %8.5lf\n", c, d, c / d);
    }
    return 0;
}

Output:

    c   root(n)  ratio
 4472  3162.278  1.41417
 6325  4472.136  1.41431
 7746  5477.226  1.41422
 8944  6324.555  1.41417
10000  7071.068  1.41421
10954  7745.967  1.41416
11832  8366.600  1.41419
12649  8944.272  1.41420
13416  9486.833  1.41417

We can see that, even though there are some 'rounding' errors, the last column appears reasonably constant (and, as it happens, an approximation to √2, which will generally improve as n becomes larger) – thus, as we ignore constant coefficients in Big-O notation, the complexity is, as you predicted, O(√n).

Adrian Mole
  • 49,934
  • 160
  • 51
  • 83
  • Be aware, however, that _testing_ for several small values proves nothing about the asymptotic behavior for large values. And each tested value is _small_ compared to infinity... :) – CiaPan Apr 25 '22 at 07:53