assigning running time

Question

I'm trying to assign running times to loops of code to roughly get the upper asymptotic ($O$) running time.

while (j < n2) {                                   # executes n2-1 times
    int k = 0;                                         
    while ((k < n1) && (seq[k] < seq2[j])) {       # executes (n2-1)*n1times    
      k = k + 1;
      }
     // we want to insert seq2[j] at seq[k]
     // so we move seq[k] through seq[n1 - 1] to the right
     for (int i = n1; i > k; i = i - 1) {         # some n-k times
        seq[i] = seq[i - 1];
      }
     seq[k] = seq2[j];
     j = j + 1;
     n1 = n1 + 1;
}

I know this is bad but would this algorithm worst running time be something in O(n^2) because there is one main loop and then two separate nested loops inside the main loop?

Thanks

Answer 1

It's hard to say without seeing the preceding code. If seq is initially empty the the run time of the outer loop is $O(n2)$ and the first nested loop is $O(k)$ and the second nested loop is $O(n1-k)$. The total running time would be $O(n2)*(O(k)+O(n1-k))$ which is $O(n^2)$.

However if seq has some initial elements, the worst case running time for the algorithm is $O(\infty)$. The problem is with the nested while loop seq[k]>seq2[j]. If any of the first n elements in seq are > seq2[j] the loop will not increment and run endlessly. Also you may run into array index out of range errors.

For example if seq = 2 , 1 , 0 and seq2 = 1 , 2 , 3. Then seq[0] > seq2[0] would be equivalent to 2 > 1 which i s false and k would never increment. The solution would be to use

n1 = sizeof(seq)/sizeof(seq[0])  # number of elements in seq
int k = 0;
for(; k < n1 ; k++){             # iterate over seq
    if( seq[k] >= seq2[j] )      # until an we find an element in seq >= seq2[j]
        break;