Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
3  
Are you familiar with Landau notation? – David Richerby Mar 28 at 16:58
4  
"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 – Auberon Mar 28 at 17:51
    
@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. – Olathe Mar 29 at 6:00
1  
@Olathe I've yet to see an algorithm that uses more than zero but less than a constant of any resource – adrianN Mar 29 at 6:49
    
@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. – Olathe Mar 29 at 7:08

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)$.

share|cite|improve this answer
    
"does not effectively depend on its input." -- for which definition of "effectively"? – Raphael Mar 28 at 18:16
    
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. – jmite Mar 28 at 18:18
    
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. – Raphael Mar 28 at 18:20
    
simple illustrative example(s) would be helpful – vzn Mar 31 at 15:35

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.

share|cite|improve this answer
3  
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. – Olathe Mar 29 at 5:56
    
@Olathe Space occupied by each input in terms of bytes and number of input in terms of the count aren't two different concept? – Prateek Mar 29 at 11:57

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.

share|cite|improve this answer
2  
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$. – Olathe Mar 29 at 5:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.