Vector stl q. no. 3

#1

why answer is O(n^2) instead of O(n)

#2

@aman17nov1999
The vector was not passed by reference, Therefore on each function call, a fresh copy of vector is created resulting in overall complexity of O(n^2).
Example:


run this code. One time without & and one time with &
It gets internal error because of memory limit exceeded
Success #stdin #stdout 0s 4508KB
done //Time for 1e4 with &
Success #stdin #stdout 0.12s 394624KB
done //Time for 1e4 without &
look at the memory used in both the cases

#3

then space complexity should be O(n^2)