The Red Penguin

Counting up time and space units


Tuesday 13 October 2020

Counting up time and space units

Things that take up 1 time unit:

memory read
memory write
numerical operations (eg + - x /)
comparison (eg >)
if
while
return

Example 1. A function with simple operations.
function F1(a,b,c)      
max = a 1 memory read (a) + 1 memory write (max) 2 time units
if (b>max) 2 memory reads (b, max) + 1 comparison (>) + 1 if instruction 4 time units
max = b 1 memory read (b) + 1 memory write (max) 2 time units
if (c>max) 2 memory reads (c, max) + 1 comparison (>) + 1 if instruction 4 time units
max = c 1 memory read (c) + 1 memory write (max) 2 time units
return max 1 memory read (max) + 1 return 2 time units

Total 16 time units


In terms of space, there is 1 simple variable created (max). So it's just 1 space unit.

You don't count the variables put into the function as we are not creating these.

Example 2. A loop, which is not a simple operation. This is a function which searches for a number in an array.
A is the array, N is the number of elements in the array and x is the number we are searching for.

function F2(A,N,x)      
for 0 <= i < N see below 7N+5 time units
if(A[i]==x) 3 memory reads (x,i,A[i]), 1 numerical op (==), 1 if
this will be executed N times 5N time units
return i only 1 of the return instructions will be executed, not both
return -1 worst case it will be the one at the end
if return = -1 it will be 1 time unit but if it is return i
it will also carry out a memory read so it will be ... 2 time units
Total 12N+7 time units

We can think of the for loop as :
i=0 1 memory write (i) 1 time unit
if(i) + 1 if instruction
but worst case - if the number is not in the array we would
check this (N+1) times. So the time units would be 4*(N+1) time units

i=i+1 1 memory read (i), 1 numerical operation (+), 1 memory write (i)
this is executed N times in worst case, so 3N time units
Total 7N+5 time units


In terms of space, we create one new variable i, so again it's just 1 space unit.

Questions.

1. How many time and space units are required by this algorithm?

x=2      1 memory write (x)
y=x+1 1 memory read (x), 1 numerical op (+), 1 memory write (y)
z=x*y 2 memory reads (x, y), 1 numerical op (*), 1 memory write (z)


8 time units, 3 space units (x,y,z)

2. How many time and space units are required by this algorithm?

y=1                    1 memory write (y)
for 0 <= i <= N 7N+12 time units (see below)
y=y*i 2 memory reads (y,i), 1 numerical op (*), 1 memory write (y), maximum N+1 times so 4(N+1) time units
Total 11N+17 units

We can think of the for loop as :
i=0 1 memory write (i) 1 time unit
if(i<=N) 2 memory reads (i, N) + 1 comparison (<=) + 1 if instruction
but worst case - if the number is not in the array we would
check this (N+2) times. So the time units would be 4(N+2) time units

i=i+1 1 memory read (i), 1 numerical operation (+), 1 memory write (i)
this is executed N+1 times in worst case, so 3(N+1) time units
Total 7N+12 time units


Space units would be 2, one for y, i (N would have been defined elsewhere?)
// note: answer given was 10N+15 which is wrong

3. For the following piece of code:

i=0
while(i<2)
i=i+1


(a) How many times is the condition checked? Answer - 3 (when i=0, 1 and 2)
(b) How many iterations are there of the whole loop? Answer - 2 (when i=0, 1)

4. How many time and space units are required by this algorithm?

i=0                   1 memory write (i) so 1
while(i<2) 1 memory read (i), 1 comparison (<), 1 while instruction - this is checked 3 times, see Q3a above so 9
i=i+1 1 memory read (i), 1 numerical op (+). 1 memory write (i) - this is iterated 2 times, see Q3b above, so 6


Total 16 time units and 1 memory unit for i