How can using strings instead of simple types like integers alter the O-notation of operations?

Question

Proposed answer:

Strings are simply arrays of characters so the O-notation will be dependent on the number of characters in the string (if the loop depends on the length of the string). In this case the O-notation wouldn't be affected because the length of the string is a constant.

Any other ideas? Am I reading this question correctly?

Answer 1

This is not true, since representing integers in arrays are not boundless.

IOW a string that represents an 32-bit integer is maximally 32-bit, thus maximally 10 digits in base 10, and O(10) is a negiable constant that doesn't change the O notation.

So, in summary, while strings are O(n), basic integer types represented as strings are O(maximally 10)=O(0)

I think you need to specify your problem better.

Answer 2

That depends entirely on what you are doing with the strings.

If you for example copy items from one array to another, the result is depending on the implementation. It's still an O(n) operation, but the meaning of n changes. If copying a string causes a new copy to be created, n means the total number of characters in all the strings. If copying a string is only copying the reference to it, n means the total number of strings.

Answer 3

Try thinking about something that operates on an array of integers or an array of strings, clearly in the latter case you have an array of array of a primitive type rather than an array of a primitive type. How does this change things?