1
$\begingroup$

I am going through a fairly non-rigorous textbook called 'Cracking the code interview' and I am bothered by this terminology called "unit of work".

It says in the textbook that certain operations take constant work, where as others take variable amount of time.

For example, adding/subtracting/multiplying/dividing two numbers take constant work. Similarly, a comparison statement also takes constant work. Lookup are also constant.

Whereas other operations such as for-loop takes a variable amount of work. For example, if a FOR-loop is to be run from $i = 0$ to $i = n-1$, and assuming whatever inside of the FOR-loop takes constant amount of time, then the total amount of work is proportional to $n$. That is, FOR-loop takes $O(n)$ time.

Something that doesn't really make sense to me is the smallest unit that can be defined as "work" in big Oh runtime analysis. What is this unit based off of? Adding two bits together? Adding two integers together?

Stemming from it are two related concerns:

  1. certainly multiplication takes more "work" than addition. Division takes more work than subtraction. So what is the smallest unit of work here? Is the time to add two numbers a smaller amount of work than multiplying two numbers? That is, is the work of multiplication proportional to the time of addition?, $\text{work}_{\times} = c \times \text{work}_{+}, c > 0?$

  2. For example, are things like multiplication truly independent of the input? $k \times n = n + n + \ldots + n$ ($k$ times). So why is it considered a constant amount of work? Doesn't the same logic also apply to other programs? Say if I have $n$ conditional statement checking if a value is smaller or greater than a number $n$. Then this "constant" operation can still depend on how large my $n$ is (depending on how i implement this comparison).

Thanks for your patience.

$\endgroup$
2
  • 1
    $\begingroup$ We implicitly work in a model of computation known as the random-access machine or RAM model. You can look it up on Wikipedia. It has also been described several times on this site, as an answer to multiple questions. $\endgroup$ – Yuval Filmus May 23 at 8:27
  • 1
    $\begingroup$ The simple answer: defining what you mean by "unit of work" is part of computing time complexity. $\endgroup$ – Jörg W Mittag May 27 at 18:36
1
$\begingroup$

We assume an efficient implementation of standard arithmetic operations (since a stupid implementation could be replaced with a better one). Of course, if the numbers were of unlimited size, the amount of time wouldn't be constant. But it would still be constant per bit (at least for addition and comparison).

So if we pretend that all numbers are a constant size ("one unit of storage") and we pretend that all additions are constant time ("one unit of work"), we get the same relationship between input size and processing time as we would if we worked it out measuring space in bits and processing time in single-bit operations: time is linear in input size.

Complexity analysis is not about nanoseconds. You can't figure out how many nanoseconds an algorithm will take just by looking at the algorithm. What we can figure out is what happens to the time if you increase the problem size. Twice as long is twice as long regardless of what the measurement unit is. The measurement unit is irrelevant as long as we use the same one throughout.

Now, if we were really doing arbitrary precision arithmetic, multiplication and division would take polynomial time. But for most algorithms, taking that into account would massively complicate the analysis without adding much new information. So it's convenient to pretend multiplication and division are linear time.

$\endgroup$
1
$\begingroup$

Something that doesn't really make sense to me is the smallest unit that can be defined as "work" in big Oh runtime analysis. What is this unit based off of? Adding two bits together? Adding two integers together?

It depends on the computational model you choose. It is obviously not true that two numbers can be added together in constant time regardless of their size. If you think about it in terms of the most elementary operations, those on individual bits, adding two $n$-bit numbers would require $O(n)$ elementary operations. And multiplying two $n$-bit numbers would use $O(n^2)$ elementary operations if you do it using long multiplication. You can easily try this out for yourself using pen and paper.

The problem with this viewpoint is that it makes analyzing algorithms very tedious. Any time we would add two numbers $a$ and $b$ we would have to figure out that they would have $\log{a}$ and $\log{b}$ bits respectively and that the addition would take $O(\log{a}+\log{b})$ time. This would make the analysis much more tedious, and result in running time with lots of $\log$s in them.

It is also not very realistic, because real-world computers do not work with individual bits, but instead have words of some natural size (e.g., $8$, $32$ or $64$ bits) and their elementary operations work on those words (in a single processor clock cycle, which is what we might consider an elementary unit of time). Thus, real-world computers can compute the addition (or multiplication or ...) of two $8/32/64$-bit integers in constant time. If we want to do artihmetic on larger integers, it would take more of these elementary operations. E.g., adding two $64$-bit integers on a $32$-bit machine would require two additions of $32$-bit integers plus a possible carry operation.

The most commonly chosen model for analyzing algorithms is the RAM model. The RAM model is a theoretical abstraction of this real-world computer. It wouldn't make sense to fix our word size to any constant, because it is unreasonable to use a computer with 8-bit words to do computations with an exabyte-scale database. The RAM model states that on an input of size $n$ (bits), we presume that the word size of our computer is $O(\log n)$ bits and that we can do artithmetic operations on integers of this size in constant time. Essentially, we presume that our computer "grows" with the size of the input and assume that we can manipulate a pointer to the input in constant time (it would be rather strange to try and handle a very large input, so large that our physical bus size is smaller than required to address the input).

certainly multiplication takes more "work" than addition

This is not something we care about in the RAM model, at least for the integers with at most $O(\log{n})$ bits on which we can do artihmetic operations in constant time. The constant for multiplication might be higher than the constant for addition, but it's still a constant and the entire point of big-$O$ notation is to hide constants.

For example, are things like multiplication truly independent of the input?

So, no. In the RAM model, if you have a really large number it can no longer be manipulated in constant time. In the RAM model, if we are analyzing an algorithm for e.g. sorting, our input will have $\Omega(n)$ bits, which means that we can manipulate numbers with up to $O(\log n)$ bits in constant time. This is convenient, because we can have a for-loop over the elements of the input and not have to worry about the time required to increment the iterator or the time required to check whether the iterator has exceeded the upper bound of the for loop, etc... This all falls within the bounds of manipulating integers with $O(\log n)$ bits in constant time.

However, once you start dealing with large numbers, much larger than the input size, this starts to break down. Consider e.g., the problem of computing the $k^\textrm{th}$ prime number. The input is just the number $k$, which has $\log{k}$ bits and this is the size of the input. This means that the largest number we can manipulate in constant time is $O(\log\log{k})$ bits -- much smaller than the $k^\textrm{th}$ prime number that we are trying to calculate.

Let's consider a simpler problem, where the input is two numbers $a,b$ given in binary and we have to compute $a+b$. If the size of our input is $n$ bits, we can solve this problem in $O(n/\log n)$ time: We can manipulate blocks of $\log n$ bits in constant time (by the RAM model), and we have to add $n/\log n$ of those blocks (with a possible carry operation between blocks) to get the final result.

This is also where you start seeing differences between simple operations such as addition and "more complex" operations such as multiplication. If we consider the variant of the previous problem where we would instead have to multiply $a\times b$ it would require more time than $O(n/\log n)$ (the precise time depending on which multiplication algorithm you choose; there are algorithms that are vastly more efficient than the long multiplication example considered previously). Many programming languages have bignum libraries that implement various algorithms for dealing with large integers that have to be represented using multiple words.

I am going through a fairly non-rigorous textbook called 'Cracking the code interview'

The main takeaway point of this (for your upcoming interview) is that you can treat arithmetic operations as taking constant time, unless the problem deals with particularily big numbers with a very succinct input. E.g., computing $\pi$ up to some number of decimal places, computing the $k^\textrm{th}$ prime number, etc,...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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