What is meant by "Constant Amortized Time" when talking about time complexity of an algorithm?
Constant Amortized Time
algorithmbig ocomplexity-theory
Related Solutions
I'll do my best to explain it here on simple terms, but be warned that this topic takes my students a couple of months to finally grasp. You can find more information on the Chapter 2 of the Data Structures and Algorithms in Java book.
There is no mechanical procedure that can be used to get the BigOh.
As a "cookbook", to obtain the BigOh from a piece of code you first need to realize that you are creating a math formula to count how many steps of computations get executed given an input of some size.
The purpose is simple: to compare algorithms from a theoretical point of view, without the need to execute the code. The lesser the number of steps, the faster the algorithm.
For example, let's say you have this piece of code:
int sum(int* data, int N) {
int result = 0; // 1
for (int i = 0; i < N; i++) { // 2
result += data[i]; // 3
}
return result; // 4
}
This function returns the sum of all the elements of the array, and we want to create a formula to count the computational complexity of that function:
Number_Of_Steps = f(N)
So we have f(N)
, a function to count the number of computational steps. The input of the function is the size of the structure to process. It means that this function is called such as:
Number_Of_Steps = f(data.length)
The parameter N
takes the data.length
value. Now we need the actual definition of the function f()
. This is done from the source code, in which each interesting line is numbered from 1 to 4.
There are many ways to calculate the BigOh. From this point forward we are going to assume that every sentence that doesn't depend on the size of the input data takes a constant C
number computational steps.
We are going to add the individual number of steps of the function, and neither the local variable declaration nor the return statement depends on the size of the data
array.
That means that lines 1 and 4 takes C amount of steps each, and the function is somewhat like this:
f(N) = C + ??? + C
The next part is to define the value of the for
statement. Remember that we are counting the number of computational steps, meaning that the body of the for
statement gets executed N
times. That's the same as adding C
, N
times:
f(N) = C + (C + C + ... + C) + C = C + N * C + C
There is no mechanical rule to count how many times the body of the for
gets executed, you need to count it by looking at what does the code do. To simplify the calculations, we are ignoring the variable initialization, condition and increment parts of the for
statement.
To get the actual BigOh we need the Asymptotic analysis of the function. This is roughly done like this:
- Take away all the constants
C
. - From
f()
get the polynomium in itsstandard form
. - Divide the terms of the polynomium and sort them by the rate of growth.
- Keep the one that grows bigger when
N
approachesinfinity
.
Our f()
has two terms:
f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1
Taking away all the C
constants and redundant parts:
f(N) = 1 + N ^ 1
Since the last term is the one which grows bigger when f()
approaches infinity (think on limits) this is the BigOh argument, and the sum()
function has a BigOh of:
O(N)
There are a few tricks to solve some tricky ones: use summations whenever you can.
As an example, this code can be easily solved using summations:
for (i = 0; i < 2*n; i += 2) { // 1
for (j=n; j > i; j--) { // 2
foo(); // 3
}
}
The first thing you needed to be asked is the order of execution of foo()
. While the usual is to be O(1)
, you need to ask your professors about it. O(1)
means (almost, mostly) constant C
, independent of the size N
.
The for
statement on the sentence number one is tricky. While the index ends at 2 * N
, the increment is done by two. That means that the first for
gets executed only N
steps, and we need to divide the count by two.
f(N) = Summation(i from 1 to 2 * N / 2)( ... ) =
= Summation(i from 1 to N)( ... )
The sentence number two is even trickier since it depends on the value of i
. Take a look: the index i takes the values: 0, 2, 4, 6, 8, ..., 2 * N, and the second for
get executed: N times the first one, N - 2 the second, N - 4 the third... up to the N / 2 stage, on which the second for
never gets executed.
On formula, that means:
f(N) = Summation(i from 1 to N)( Summation(j = ???)( ) )
Again, we are counting the number of steps. And by definition, every summation should always start at one, and end at a number bigger-or-equal than one.
f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )
(We are assuming that foo()
is O(1)
and takes C
steps.)
We have a problem here: when i
takes the value N / 2 + 1
upwards, the inner Summation ends at a negative number! That's impossible and wrong. We need to split the summation in two, being the pivotal point the moment i
takes N / 2 + 1
.
f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )
Since the pivotal moment i > N / 2
, the inner for
won't get executed, and we are assuming a constant C execution complexity on its body.
Now the summations can be simplified using some identity rules:
- Summation(w from 1 to N)( C ) = N * C
- Summation(w from 1 to N)( A (+/-) B ) = Summation(w from 1 to N)( A ) (+/-) Summation(w from 1 to N)( B )
- Summation(w from 1 to N)( w * C ) = C * Summation(w from 1 to N)( w ) (C is a constant, independent of
w
) - Summation(w from 1 to N)( w ) = (N * (N + 1)) / 2
Applying some algebra:
f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )
f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )
f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )
=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )
f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )
=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 =
(N / 2 - 1) * (N / 2) / 2 =
((N ^ 2 / 4) - (N / 2)) / 2 =
(N ^ 2 / 8) - (N / 4)
f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )
f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)
f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)
f(N) = C * ( N ^ 2 / 4 ) + C * N
f(N) = C * 1/4 * N ^ 2 + C * N
And the BigOh is:
O(N²)
There's a simple trick for this problem:
bool IsPowerOfTwo(ulong x)
{
return (x & (x - 1)) == 0;
}
Note, this function will report true
for 0
, which is not a power of 2
. If you want to exclude that, here's how:
bool IsPowerOfTwo(ulong x)
{
return (x != 0) && ((x & (x - 1)) == 0);
}
Explanation
First and foremost the bitwise binary & operator from MSDN definition:
Binary & operators are predefined for the integral types and bool. For integral types, & computes the logical bitwise AND of its operands. For bool operands, & computes the logical AND of its operands; that is, the result is true if and only if both its operands are true.
Now let's take a look at how this all plays out:
The function returns boolean (true / false) and accepts one incoming parameter of type unsigned long (x, in this case). Let us for the sake of simplicity assume that someone has passed the value 4 and called the function like so:
bool b = IsPowerOfTwo(4)
Now we replace each occurrence of x with 4:
return (4 != 0) && ((4 & (4-1)) == 0);
Well we already know that 4 != 0 evals to true, so far so good. But what about:
((4 & (4-1)) == 0)
This translates to this of course:
((4 & 3) == 0)
But what exactly is 4&3
?
The binary representation of 4 is 100 and the binary representation of 3 is 011 (remember the & takes the binary representation of these numbers). So we have:
100 = 4
011 = 3
Imagine these values being stacked up much like elementary addition. The &
operator says that if both values are equal to 1 then the result is 1, otherwise it is 0. So 1 & 1 = 1
, 1 & 0 = 0
, 0 & 0 = 0
, and 0 & 1 = 0
. So we do the math:
100
011
----
000
The result is simply 0. So we go back and look at what our return statement now translates to:
return (4 != 0) && ((4 & 3) == 0);
Which translates now to:
return true && (0 == 0);
return true && true;
We all know that true && true
is simply true
, and this shows that for our example, 4 is a power of 2.
Related Topic
- What does O(log n) mean exactly
- Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing
- Ukkonen’s suffix tree algorithm in plain English
- How to building a heap be O(n) time complexity
- C++ – Image Processing: Algorithm Improvement for ‘Coca-Cola Can’ Recognition
- How to find time complexity of an algorithm
- R – How to actually replace a resources (.resx) file in a running application for a .Net DLL
- Python – SQLAlchethe session management in long-running process
Best Answer
Amortised time explained in simple terms:
If you do an operation say a million times, you don't really care about the worst-case or the best-case of that operation - what you care about is how much time is taken in total when you repeat the operation a million times.
So it doesn't matter if the operation is very slow once in a while, as long as "once in a while" is rare enough for the slowness to be diluted away. Essentially amortised time means "average time taken per operation, if you do many operations". Amortised time doesn't have to be constant; you can have linear and logarithmic amortised time or whatever else.
Let's take mats' example of a dynamic array, to which you repeatedly add new items. Normally adding an item takes constant time (that is,
O(1)
). But each time the array is full, you allocate twice as much space, copy your data into the new region, and free the old space. Assuming allocates and frees run in constant time, this enlargement process takesO(n)
time where n is the current size of the array.So each time you enlarge, you take about twice as much time as the last enlarge. But you've also waited twice as long before doing it! The cost of each enlargement can thus be "spread out" among the insertions. This means that in the long term, the total time taken for adding m items to the array is
O(m)
, and so the amortised time (i.e. time per insertion) isO(1)
.