I recently came across a problem that made me wonder. What if I stored a N element array inside an array of length N across all the N indexes. As a tiny example:
[
[1, 2, 3],
[5, 6, 7],
[8, 9, 10],
]
An array of length 3 and at every index there is an array again of length 3
What would be the space complexity? Is it still O(N) or has it change.
It would still be O(n) because the Space Complexity analysis is meant to describe the complexity of the relationship between n and space, it doesn't care if you store an array of 3 elements at every index. The space used will be 3 times higher but still the relationship will be linear.
Big-O notation describes an asymptotic upper bound. It represents the algorithm’s scalability and performance.
Simply put, it gives the worst-case scenario of an algorithm’s growth rate.
from here.
It would be different if you said that at every index an array of N=index elements is stored. In that case it would have been O(n^2).
