educative.io

Space Complexity really only O(n)?

Courses
,
#1

To me this doesn’t make sense. If you want to generate this output list of all permutations. The list will grow O(n!) as well.

Can somebody elaborate why it would only be O(n)?

Output 2: [[Frozen, Dune, Coco, Melificient][Frozen, Dune, Melificient, Coco][Frozen, Coco, Dune, Melificient][Frozen, Coco, Melificient, Dune][Frozen, Melificient, Coco, Dune][Frozen, Melificient, Dune, Coco][Dune, Frozen, Coco, Melificient][Dune, Frozen, Melificient, Coco][Dune, Coco, Frozen, Melificient][Dune, Coco, Melificient, Frozen][Dune, Melificient, Coco, Frozen][Dune, Melificient, Frozen, Coco][Coco, Dune, Frozen, Melificient][Coco, Dune, Melificient, Frozen][Coco, Frozen, Dune, Melificient][Coco, Frozen, Melificient, Dune][Coco, Melificient, Frozen, Dune][Coco, Melificient, Dune, Frozen][Melificient, Dune, Coco, Frozen][Melificient, Dune, Frozen, Coco][Melificient, Coco, Dune, Frozen][Melificient, Coco, Frozen, Dune][Melificient, Frozen, Coco, Dune][Melificient, Frozen, Dune, Coco]]

=> This looks like 4 movies = 24 entries or 4!

Thanks

Course: Decode the Coding Interview in C#: Real-World Examples - Learn Interactively
Lesson: Feature #3: Generate Movie Viewing Orders - Decode the Coding Interview in C#: Real-World Examples

#2

Hi @Jens_Wachtel
Space complexity cannot be “O(n!)” it will be “O(n)”. Because space depends on recursion depth which is “O(n)”.

#3

Sorry this still does not make sense to me but thanks for explaining!
If space would depend on recursion depth O(n), but reality (to me) appears that I have to occupy memory of 24 lists now. Those lists reference each 4x strings in memory.

What if you’d process a permutation of 20 movies and return the user List<List> of it?
I hardly doubt I would have to account for let’s say max. 40 chars per movie = 40chars2bytes20movies in terms of space complexity?
In reality the produced result would need much more memory