CODEWITHSUNDEEP
algorithmdata-structurestime-complexitycomputer-sciencecomplexity-theory
Amir
Amir

Reputation: 11

How can I calculate the time function T(n) of the following code?

x=0;
for(int i=1 ; i<=n ; i++){
    for(int j=1 ; j<=n ; j++){
        x++;
        n--;
    }
}

By testing the code, the nested FOR loop recurs ⌈n/2⌉ times per steps of the first For loop.

But I don't know how to formulate these rules with sigmas. I would really appreciate if anyone can help me with this.

Upvotes: 1

Views: 1265

Answers (3)

Fenix phoenix
Fenix phoenix

Reputation: 78

Let's compute the exact value of x.

TL;DR: x(N) = N-[N/2^i+1], where i is the lowest number, satisfying the condition: (i+1) 2^i > N. As Mariano Demarchi said, T(N)=O(N).

First we will check how variables change after each inner loop. Let we have (n, i, x) values between 2 and 3 lines in code (before the inner loop):

  • How many iterations will happens? Each iteration increases j and decreases n, so the distance between them decreases by two. Start distance is n-1, and final, after the loop, is 0 (if n is odd) or -1 (if n is even). Thus if n=2k, the answer is k, otherwise k+1. So, the inner loop makes [(n+1)/2] = d iterations.
  • Thus x will increase by d, n becomes n-d and i becomes i+1.
  • (n, i, x) -> (n-d, i+1, x+d) or equal ([n/2], i+1, x + [(n+1)/2])

Now concentrate on values of n and i variables in the big loop:

  • They changes like that: (n, i) -> ([n/2], i+1)
  • The stop-condition is [N/2^i] < i+1, which is equals to (i+1)*2^i > N. Of course, we need minimal i, satisfying the condition.

So, i is the first number satisfying the condition and we DO NOT SUM further:

    x = [(N+1)/2] + [([N/2]+1)/2] + [([N/2^2]+1)/2] + ... + [([N/2^i-1]+1)/2]

By the number theory magic (not related on this question) this series is equals to N (1-1/2^i+1). Particularly, if N is a power of 2 minus 1, we can see it easily.

So, this code returns exactly the same value in O(log(N)) time.

// finding i
unsigned long long i = 0;
while ((i + 1) * (1ll << i) < n)
    ++i;

// finding x
x = n - (n >> (i + 1));

Upvotes: 1

Vineet Jain
Vineet Jain

Reputation: 1575

You can express T(n) as T(n-2)+1, i.e. T(n)=T(n-2)+1 Or its expected time complexity is O(n/2) => O(n).

Edit: T(n-2)+1 expression is evaluated as you can see if you increase n-2 by 2 means when n-2 became n, the number of times the loop will be executed is the 1 + number of time loop executed for n-2. 1 is because you are incrementing j and decrementing n simultaneously. it is exactly the same as incrementing j by 2.

Upvotes: 1

Mariano Demarchi
Mariano Demarchi

Reputation: 345

In the inner loop, given that n decrements at the same time that j increments, n is going to be lower than j at the middle of the difference between both initial values, that is (n-1)/2. That's why your tests show that the inner loop runs ⌈n/2⌉ times per each iteration of the outer loop.

Then the outer loop is going to stop when for the i that satisfies this equality n/2^i = i-1. This affects the outer loop stopping condition.

T(n)

=

n/2 + T(n/2)

=

n/2 + n/4 + T(n/4)

=

n (1/2 + 1/4 + ... + 1/(2^i))

This series converges to n so that algorithm is O(n).

Upvotes: 0

Related Questions