Geek Answers Handbook

Growth order as a function of N

I understand the complexity of the algorithm, I thought that all the codes below are quadratic in terms of growth order, but since I need the growth order as a function of N, I think that things change, and I don’t know exactly how it works.

int sum = 0;
    for(int n = N; n > 0; n/=2)
    for(int i = 0; i < n; i++)
    sum++

int sum = 0;
    for(int i = 1; i < N; i*=2)
    for(int j = 0; j < i; j++)
    sum++

int sum = 0;
    for(int i = 1; i < N; i*=2)
    for(int j = 0; j < N; j++)
    sum++
+4
source share
1 answer
int sum = 0;
    for(int n = N; n > 0; n/=2)
    for(int i = 0; i < n; i++)
    sum++

This O(N), the inner loop runs just N + N/2 + N/4 + ... + 1once, this sum converges to 2Nwhen N->infinity, and therefore, it is O(N).

int sum = 0;
    for(int i = 1; i < N; i*=2)
    for(int j = 0; j < i; j++)
    sum++

This is very similar to case1, and I'm going to leave it to you as a practice. Follow the same approach that I did there and you will get an answer.

int sum = 0;
    for(int i = 1; i < N; i*=2)
    for(int j = 0; j < N; j++)
    sum++

, . , i N .

, , , N.

.

+7

More articles:


All Articles