Is objectForKey slow for big NSDictionary?

The CFDictionary section of the Collections Programming Topics for Core Foundation (which you should look into if you want to know more) states:

A dictionary—an object of the CFDictionary type—is a hashing-based collection whose keys for accessing its values are arbitrary, program-defined pieces of data (or pointers to data). Although the key is usually a string (or, in Core Foundation, a CFString object), it can be anything that can fit into the size of a pointer—an integer, a reference to a Core Foundation object, even a pointer to a data structure (unlikely as that might be).

This is what wikipedia has to say about hash tables:

Ideally, the hash function should map each possible key to a unique slot index, but this ideal is rarely achievable in practice (unless the hash keys are fixed; i.e. new entries are never added to the table after it is created). Instead, most hash table designs assume that hash collisions—different keys that map to the same hash value—will occur and must be accommodated in some way. In a well-dimensioned hash table, the average cost (number of instructions) for each lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of key-value pairs, at constant average (indeed, amortized) cost per operation.

The performance therefore depends on the quality of the hash. If it is good then accessing elements should be an O(1) operation (i.e. not dependent on the number of elements).

EDIT:

In fact after reading further the Collections Programming Topics for Core Foundation, apple gives an answer to your question:

The access time for a value in a CFDictionary object is guaranteed to be at worst O(log N) for any implementation, but is often O(1) (constant time). Insertion or deletion operations are typically in constant time as well, but are O(N*log N) in the worst cases. It is faster to access values through a key than accessing them directly. Dictionaries tend to use significantly more memory than an array with the same number of values.

NSDictionary is essentially an Hash Table structure, thus Big-O for lookup is O(1). However, to avoid reallocations (and to achieve the O(1)) complexity you should use dictionaryWithCapacity: to create a new Dictionary with appropriate size with respect to the size of your dataset.