How can i get the Big O Notations in this while loop of C Language code?-CodePudding

I have a little question about the Big-O notation in C Language code below.

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, the k(k 1)/2 = n.
So, I think O(root(n)) is the answer.

Is that right solution about this question?

CodePudding user response：

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 = floor(0.5) i^2 = O(i^2)

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

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

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

CodePudding user response：

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("]  %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).