I have the definition of an in-situ algorithm from the professor, but I don't understand it.
In-situ algorithms refer to algorithms that operate with Θ(1) memory.
What does that mean?
$\begingroup$
$\endgroup$
8
-
3$\begingroup$ Are you familiar with Landau notation? $\endgroup$– David RicherbyCommented Mar 28, 2016 at 16:58
-
4$\begingroup$ "An algorithm is said to be an in situ algorithm, or in-place algorithm, if the extra amount of memory required to execute the algorithm is O(1), that is, [memory] does not exceed a constant no matter how large the input. For example, heapsort is an in situ sorting algorithm." en.wikipedia.org/wiki/In_situ#Computer_science $\endgroup$– AuberonCommented Mar 28, 2016 at 17:51
-
$\begingroup$ @Auberon, it should be added that $\Theta(1)$ imposes a further requirement than $O(1)$: that the total memory used in any particular invocation does not fall below a constant no matter the size of the input. $\endgroup$– OlatheCommented Mar 29, 2016 at 6:00
-
1$\begingroup$ @Olathe I've yet to see an algorithm that uses more than zero but less than a constant of any resource $\endgroup$– adrianNCommented Mar 29, 2016 at 6:49
-
$\begingroup$ @adrianN, AES encryption of files is done with RAM usage under a constant upper bound. You process a block at a time, each block needs the same amount of RAM to be processed, and the RAM can be reused from one block to the next. A simpler example is to convert all the letters in an ASCII-encoded file to uppercase. You can read in a block, say 4096 bytes, of the file, process that 4096 bytes, write the results of that block, and reuse the same RAM for the next block. $\endgroup$– OlatheCommented Mar 29, 2016 at 7:08
|
Show 3 more comments
3 Answers
$\begingroup$
$\endgroup$
4
First, let's unpack what $\Theta(1)$ means.
Big $O$, and big $\Theta$, are classes of functions. There's a formal definition here, but for the purposes of this question, we say that a function $f$ is in $O(1)$ if there's a constant $c$ where, for all $x$, $f(x) \leq C$. That is, $f$ grows at most as fast as a constant function.
Big-$\Theta$ doesn't mean much for constant functions, because when describing algorithm time or space usage, there isn't much below constant. But to explain what it means, $f \in \Theta(1)$ if there are some constants $c,d$ such that, for all $x$, $d \leq f(x) \leq c$. That is, $f$ grows at least as fast, and at most as fast, as a constant function.
Now what does this have to do with memory usage? Consider some algorithm $A$. There is some (mathematical) function which, given an input $n$, gives the maximum memory usage of your algorithm $A$ on any input of size $n$. Let's call this function $mem$.
So, now we combine our two concepts. If an algorithm uses $\Theta(1)$ memory, then its memory usage function is in $\Theta(1)$, meaning that there exists some $d,c$ such that, for any input, the memory used is between $d$ and $c$.
In short, this means that the memory usage of the algorithm is in some constant range, regardless of the input.
Usually, the memory function does not account for the memory used to store the input to the algorithm, since otherwise memory usage would always be at least $\Theta(n)$.
answered Mar 28, 2016 at 17:51
-
$\begingroup$ "does not effectively depend on its input." -- for which definition of "effectively"? $\endgroup$– RaphaelCommented Mar 28, 2016 at 18:16
-
$\begingroup$ As in, the memory used can change depending on the input, but only within a fixed interval. Feel free to edit it if you can think of a better wording. $\endgroup$ Commented Mar 28, 2016 at 18:18
-
$\begingroup$ I don't think there is a better wording than "the memory used is between $d$ and $c$ for any input". Nor is there a need for one. $\endgroup$– RaphaelCommented Mar 28, 2016 at 18:20
-
$\begingroup$ simple illustrative example(s) would be helpful $\endgroup$– vznCommented Mar 31, 2016 at 15:35
$\begingroup$
$\endgroup$
2
Constant space complexity of algorithm
Amount of memory your algorithm uses is independent of input.
An algorithm is said to have constant space complexity if it makes use of fixed amount of space. It can be $10$ variables or an array of exactly $10$ elements.
However, In-situ algorithms perform their intended function on the input itself and thus require very little or no extra space. The input is usually overwritten by the output as the algorithm executes. (ref)
In-situ algorithms do not consider the space occupied by the input and take only the extra space into account, while calculating space complexity.
-
3$\begingroup$ This is incorrect. For example, it may be that, for a particular algorithm, inputs of less than three characters use 5 bytes of memory while all larger inputs use a million bytes of memory. That algorithm's memory use would definitely not be independent of input, but it would definitely use $\Theta(1)$ space. To correct the statement, there are constant upper and lower limits to memory use that are independent of input. $\endgroup$– OlatheCommented Mar 29, 2016 at 5:56
-
$\begingroup$ @Olathe Space occupied by each input in terms of bytes and number of input in terms of the count aren't two different concept? $\endgroup$– PrateekCommented Mar 29, 2016 at 11:57
$\begingroup$
$\endgroup$
1
That means that additional memory amount required for algorithm is not greater than some constant amount that doesn't depend on input size for sufficiently big input.
-
2$\begingroup$ It's also not less than some (perhaps other) constant amount, since $\Theta$ is the intersection of $O$ and $\Omega$. With another example, $O(x^2)$ allows functions like $f(x) = 3x^2$ and also $f(x) = x$. On the other hand, $\Theta(x^2)$ is more strict, allowing only functions of the same complexity like $f(x) = 3x^2$ but disallowing those of lesser complexity like $f(x) = x$. $\endgroup$– OlatheCommented Mar 29, 2016 at 5:44