 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 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 unitsTotal 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 unitsTotal 12N+7 time unitsWe can think of the for loop as :i=0                   1 memory write (i)                                                1 time unitif(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 unitsTotal                                                                                   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 unitsTotal                  11N+17 unitsWe can think of the for loop as :i=0                   1 memory write (i)                                                1 time unitif(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 unitsTotal                                                                                   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=0while(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 1while(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