Order of growth of as function of N

Question

I'm practicing with algorithm complexities, I thought all the codes below were quadratic in terms of the order of growth but since I need the order of growth as a function of N, I think that changes things and I don't know exactly how to work it out.

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++

Answer 1

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

This is O(N), the inner loop runs total of N + N/2 + N/4 + ... + 1 times, this sum converges to 2N when N->infinity, and thus 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 am going to leave it to you as practice. Follow the same approach I did there, and you will get the answer.

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

Here, the main difference is the inner loop does not depend on the variable of the outer loop. This means, regardless of value of i, inner loop is going to repeat N times.

So, you need to realize how many times the outer loop will repeat, and multiply it with N.

I leave it as well for you as practice after explaining these guidelines.