What is the space complexity of iterating over keys in NSMutableDictionary?

Question

Trying to determine run-time and space complexity of a HashTable (NSMutableDictionary) based solution following question:

Implement a TwoSum interface that has 2 methods: Store and Test. Store adds an integer to an internal data store and Test checks if an integer passed to Test is the sum of any two integers in the internal data store.

There seem to be many answers with varying store and test complexities. One promising one is

Have a Hashtable called StoreDict. I.e. NSMutableDictionary <NSNumber *, NSNumber *> *StoreDict as the internal data structure

1. Store(N) is implemented as

   • Check if StoreDict[@(N)] exists. If yes, increment count, I.e: StoreDict[@(N)] = @([StoreDict[@(N)] intValue]++)

2. Test(N) implemented as

   • Iterate through all keys. For each key, K,

     If [K intValue] != N/2 check if StoreDict[@(N-[K intValue])] exists

     If [K intValue] == N/2 check if [StoreDict[@(K)] intValue] >= 2

Looks like store is O(1) and Test is O(N) run-time complexity. The only question is what is the space complexity of iterating through all the keys, is it O(1) or O(N)? I.e are the keys given one-by-one (o(1) space) or are all N put into some temporary array (o(N) space)?

EDIT

I am referring to using following code to get the keys

NSEnumerator *enumerator = [StoreDict keyEnumerator];
id key;

while ((key = [enumerator nextObject])) {
    /* code that uses the returned key */
}

If it is O(N) space complexity, any better solution that gets O(1) time and space complexity for this question?

or is the keyEnumerator similar to using [StoreDict allKeys] which is O(N) space complexity?

Answer 1

NS(Mutable)Dictionary is bridged to CFDictionary and is it reasonable to hypothesise that methods of the former are implemented in terms of functions on the latter. You can test this hypothesis by placing breakpoints on CFDictionary functions and then calling NS(Mutable)Dictionary methods.

Where will this get you? Well the source of CFDictionary is available from Apple, and with that you should be able to figure out the complexities you are after.

HTH