## 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

More posts in ads2

- Counting up time and space units