Whats the complexity of adding\removing objects in NSMutableArray? [closed]

Question

I think that to add an object we need: create new array with a bigger size + make a copy of older array + add an element. So final complexity is O(N), where N - final number of elements.

Removing - O(N) also.

Am I wrong?

Thx.

Answer 1

I think that to add an object we need: create new array with a bigger size + make a copy of older array + add an element.

NOOOoooo....

To add an object, no new arrays are created and done all those stuffs.

If you remember cocoa has all pointers. And if you see C/C++ with pointers, just take it as a linked list. To add a new element only its address is saved in the list, and head/tail is adjusted if required.

Same case is here with MutableArrays.

Complexity should be O(1).