If you’re loading objects from a database and you know exactly how many objects you have, you would likely get the best performance from NSMutableArrays arrayWithCapacity: method, and adding objects to it until full, so it allocates all the memory at once if it can.
Behind the scenes, they’re secretly the same thing – *NSArray and NSMutableArray are both implemented with CFArrays via toll free bridging (a CFMutableArrayRef and a CFArrayRef are typedef’s of the same thing, __CFArray *)
NSArray and NSMutableArray should have the same performance/complexity (access time being O(lg N) at worst and O(1) at best) and the only difference being how much memory the two objects would use – NSArray has a fixed limit, while NSMutableArray can use up as much space as you have free.
The comments in CFArray.h have much more detail about this.
*: As Catfish_Man points out below, this isn’t true anymore.