2

Lets say I get N objects as input, and I need to rearrange them into a different data structure. This means the space complexity of my algorithm will be O(N). But what if I replace the objects with pointers to objects? I'll still have N pointers, but will it still be O(N) space complexity despite the fact that there is clearly going to be less memory taken?

  • 5
    yes -- O(N) is about the limits or extremes, so even if your objects are 10K in size, when N gets into the billions or trillions, the difference between 10K and 8 bytes becomes insignificant. However, big-O notation useful for thinking about limits -- in a practical sense your environment limitations will be a lot lower with just pointers (unless they are pointers to byte ;) ) – Rob Jan 15 '15 at 2:07
  • 1
    Unless you're working in C++, all objects are reference types anyway, so the distinctions you're trying to draw doesn't make much sense. (And if you are working in C++, you've got bigger problems to worry about!) – Mason Wheeler Jan 15 '15 at 2:17
1

Let's get philosophical for a minute.

Has the number of objects changed from N? No? Then it is still O(N) because you started with the premise that N was the number of input objects and that was what was chosen to measure against.

Now you could start with a different premise for a given data structure, say in a case where the individual data structures is actually a complex unit itself. Sometimes that might make sense.

Now for examples.

With regards to your original question, suppose you have a list of integers to sort. If you state that your space complexity is O(N), it doesn't matter whether you choose a 16 bit integer or a 64 bit integer or a 32 bit pointer to an 8 bit integer from a "big-Oh" perspective - it's still O(N) because you're measuring the number of items to sort.

But now suppose you wish to upgrade to support any length of integer rather than bounding the problem. Now, technically your space complexity is still O(N). But if you start dealing with large numbers, variation in number size eventually has to lead to variation in underlying data structure size. This means that measuring with respect to N may no longer make sense, and you as an intelligent programmer decide to pick something different to measure and analyze. Maybe now you want to start to think of space complexity with respect to digits instead!

  • In the last paragraph, it might be more accurate to say that space complexity is now O(mn) instead of O(n), where m stands for length of integer. – Nathan Tuggy Jan 15 '15 at 6:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.