BASIC’s renum

Exercise 3.3

A BASIC program consists in a set of instructions numbered in increasing order. The control flow is managed through the instructions GOTO x and GOSUB x, where x is the instruction’s number. For example, the following program calculates the factorial of a number:

50 INPUT N
60 LET F = 1
61 LET I = 1
73 IF I=N THEN GOTO 99 
76 LET F = F*I
80 LET I = I+1
81 GOTO 73
99 PRINT F

The procedure RENUM renumerates the instructions of the program in such a way that the lines go 10 by 10. For example, after renumerating the previous program it reads as follows:

10 INPUT N
20 LET F = 1
30 LET I = 1
40 IF I=N THEN GOTO 80 
50 LET F = F*I
60 LET I = I+1
70 GOTO 40
80 PRINT F

Describe how to implement the procedure RENUM in linear time on average.