Is this method O(log N) or constant time?

Question

I have a method that inserts elements into a priority queue. I want to know the performance time it has.

I believe it can be O(1) if the element being inserted can be place at the bottom of the queue. However, it runs on O(log N) time, if the element to be inserted is the new minimum and is percolated all the way to the root. Is this reasoning correct?

Here is the method insertion method:

/**
 * Insert into the priority queue, maintaining heap order.
 * Duplicates are allowed.
 * @param x the item to insert.
 */
public void insert( AnyType x )
{
    if( currentSize == array.length - 1 )
        enlargeArray( array.length * 2 + 1 );

        // Percolate up
    int hole = ++currentSize;
    for( array[ 0 ] = x; x.compareTo( array[ hole / 2 ] ) < 0; hole /= 2 )
        array[ hole ] = array[ hole / 2 ];
    array[ hole ] = x;
}

Answer 1

I would say "No" in answer to your question "is this reasoning correct?" Typically the O() notation is taken as an indication of worst-case complexity of an algorithm. Sometimes it can be used for average-case complexity, but rarely for best-case complexity. (See here for an example when you might use it.) You have argued that the algorithm is O(1) in the best-case circumstances, but not that it is O(1) in average or worst-case circumstances.

Leaving aside the concern about the complexity of the enlargeArray() function (which may well make this more than O(log N) although its amortized time is not, but on the other hand is not really part of the "algorithm proper" anyway because you could always pre-allocate the array to be "big enough"), I would say that your insertion algorithm is O(log N) because this is both the average and worst case complexity.

Answer 2

Both Luiggi and mkrakhin are correct: The enlargeArray call can be O(n) if you need to enlarge the array, but since that you keep doubling the size of the array, in the long run it will only happen a logarithmic number of times so the whole thing will amortize to be O(log N).

However, I think the real question you were asking is if this algorithm is O(1) if the new element is the smallest and the answer to that is "yes, as long as you don't need to call enlargeArray". The way to see that is to notice that you would go through your for loop exactly 0 times, so the only "work done" would be:

int hole = ++currentSize;
array[0] = x;
array[hole] = x;

Note: I think this also seems to indicate bug in that case (you've put the same element at the beginning and end of the array when, I think, you want to swap).