Menu
If the above condition in a programming question is given and I am solving it using recursion then am I violating the constraints? It could be because recursion also uses stack? Is it right?
918
7. o(1) space complexity means that the amount of memory that you use is constant and does not depends on the data that it is processing, more information here.
Space complexity of O(n) means that for each input element there may be up to a fixed number of k bytes allocated, i.e. the amount of memory needed to run the algorithm grows no faster than linearly at k*N.
It means, the auxiliary space size, doesn't depends on the length of input array. 4. oscrhong 1. May 22, 2018 9:09 PM. Yes, your solution uses linear extra space O(n), meaning that the space needed scales linearly with respect to the size of the input.
Unless you explicitly allocate a whole other array, make a copy of the linked list, or something of this sort in the algorithm, it will be O(1) in terms of space complexity.
If the depth of the stack (recursion) is constant and does not change with respect to the size of the input, then a recursive solution can be O(1) extra space.
Some compilers may do tail call optimization (TCO) and remove recursive calls if they are the last statement executed in any given code path through a function. With TCO, there is no call-stack related memory overhead.
However, keep in mind that the O(1) constraint may be being imposed to force you to choose a particular (probably non-recursive) algorithm, so relying on tail call optimisation may be unwise even if you know the compiler you are using has made the relevant transformation to your code. At the very least, if you rely on it, you should say so explicitly and justify your expectation that TCO will occur by reference to language specifications, compiler documentation and/or disassembly as appropriate.
83
extra allowed space is O(1)
means that your program can use only a constant amount of space, say C.
Going by the definition of big-O, this means that the space that your program needs cannot depend on the size of the input, although C can be made arbitrarily large.
So if the recursion depends on the input a (which usually is the case), the space that your program needs is not O(1).
To clarify further :
A program which always uses 1 Mb uses O(1) space.
A program which always uses 1 Tb is using O(1) space b.
A program which uses N Mb, where N is a part of the input, does not use O(1) space, (it uses O(N) space).
Long story short, whenever you read O(1), just mentally replace it with constant.
a. For example, foo(n) = foo(n - 1), the stack space needed here to maintain the function calls is O(n).
b. When material on O notation comments on how the ignored constants can be troublesome, this is what they are talking about.
42
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
