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.