The Big O Notation

Question

Suppose we are given the following program segment:

F(x) = 0
Input n
For x = 1 to x = n
y = x*(x+3)+2
Print y
Next x

1. Determine the number of steps the program will execute before entering the loop.
2. Determine the number of steps the program will execute each time it passes through the loop.
3. Determine the total number of steps that will be executed by the program if the value of n is 3,4,5
4. Determine a function that provides the number of steps that will be executed for a general value of n. You should be able to incorporate your work from steps 1 -3 to help you develop a function in the form f(n) = ... When you compute f(3), f(4), and f(5), you should get your results for step 3.
5. Using the definition of O, show that the function f you found in step 4 is O(n). This means that the algorithm is O(n)

Answer 1

1. Determine the number of steps the program will execute before entering the loop.

There are two preliminary steps:

     F(x) = 0
     Input n

 

2. Determine the number of steps the program will execute each time it passes through the loop.

  This is a "For..Next" loop.  there are two steps in the body of the loop:

    y = x*(x+3)+2

    Print y

 

 

3. Determine the total number of steps that will be executed by the program if the value of n is 3,4,5

 

    When n=3, there are 2 initial steps, 3*(2 loop and 2 body; note: some methods don't count loop control statements) steps   = 2+3*4=14

    When n=4 and n=5  (you can do)

4. Determine a function that provides the number of steps that will be executed for a general value of n. You should be able to incorporate your work from steps 1 -3 to help you develop a function in the form f(n) = ... When you compute f(3), f(4), and f(5), you should get your results for step 3.

 

     y = 2+4n

5. Using the definition of O, show that the function f you found in step 4 is O(n). This means that the algorithm is O(n)

     The function, y=2 + 4n, is first order.  So, it is O(n).    

     [note: if the function were y=14+4n², for example, then it would be O(n²)]