educative.io

Educative

Is the n + n-1 ... space complexity wrong?

a b c
→ a b c d

assuming both with product lower than target

while going from first to second
only
d, d c, d c b, d c b a
are added
(as cba, cb, c were added previous run)

hence it should be n not n(n+1)/2?

Hi @Shivam_Anand, thank you for reaching us. The space complexity we’ve calculated in our lesson is for the function that is computing the sub-arrays with the product less than the target, however in the main code we’ve just given two independent use-case examples so they have their own individual space complexity.
Hope this makes your query clear. Happy learning :slightly_smiling_face:.