CODEWITHSUNDEEP
algorithmtime-complexity
leshkari
leshkari

Reputation: 33

What is the total running time of the following code:

What is the total running time of the following code:

I concluded that this code takes O(N log N) times to perform, when the class is being created the loop takes O(N) time to perform, where this for-loop below takes log n time. But I am not completely sure about it, thats why I am asking here.

Z z = new Z(N); 
for (int i = 0; i < N-1; i = i+2) 
  z.update(i,i+1);

Class Z:

public class Z
{ 

int[] next, prev;
Z(int N)
{
    prev = new int[N];
    next = new int[N];
    for (int i = 0; i<N; ++i)
    // put element i in a list of its own
    {
     next[i] = i;
     prev[i] = i;
        }
     }

 int first(int i)
    // return first element of list containing i
 {
     while (i != prev[i]) i = prev[i];
     return i;
 }

 int last(int i)
 // return last element of list containing i
 {
     while (i != next[i]) i = next[i];
     return i;
 }


 void update(int i, int j)
 {
     int f = first(j);
     int l = last(i);
     next[l] = f;
     prev[f] = l;
 }

 boolean query(int i, int j)
 {
 return last(i) == last(j);
 }
 }

Upvotes: 1

Views: 829

Answers (3)

Kittsil
Kittsil

Reputation: 2487

The total running time is only O(N).

The constructor's loop has O(N) steps. It creates the next/prev arrays as [0, 1, ..., N].

z.update(i,i+1) takes only O(1) time. Since you only call update() once for each i=i and j=i+1, first(j) and last(i) will return j and i, respectively.

It is not possible to analyze the expected complexity of first() and last() under general conditions, as they could easily contain infinite loops (for instance, if called with 0 when next=[1,0]). However, in the example given, they will always skip the while loop entirely, as each call to these functions is on an index that has not yet been modified.

Upvotes: 1

Shadi Shaaban
Shadi Shaaban

Reputation: 1720

Here is my analysis:

Z z = new Z(N); // O(n)
for (int i = 0; i < N-1; i = i+2)  // O(n)
 z.update(i,i+1); // O(1)

Hence, the total running time will be O(n).

int first(int i)
{
    while (i != prev[i]) i = prev[i]; // O(1),  i will always equal prev[i]
                                      // for any input n > 0
    return i;
}

int last(int i)
{
    while (i != next[i]) i = next[i]; // O(1),  i will always equal next[i] 
                                      // for any input n > 0
    return i;
}    

void update(int i, int j)
{
 int f = first(j); // O(1)
 int l = last(i);  // O(1)
 next[l] = f; // O(1)
 prev[f] = l; // O(1)
}

Upvotes: 0

questioner and answerer
questioner and answerer

Reputation: 680

Your for loop takes O(N) time. You run it a total of N/2 times and because you ignore the constant this is N. Total runtime O(N^2). There is no logarithm.

Upvotes: 0

Related Questions