-1

enter image description here

Hello Stack Users, I am having trouble finishing this growth according to size algorithm problem. I was able to figure out the first two of the problem which are not listed in the picture. That would be 1. O(1) and 3. O(N) I was able to place these into their correct slots. I still cannot figure out how to determine the growth rate for 2,4,5,6 into the slots provided. Any suggestions on how to determine this?

hotrod28
  • 45
  • 8
  • 1
    The second one would be O(N^2) since it loops from [1,N] and [1,N] again inside each of those – faris Sep 09 '18 at 21:59

1 Answers1

2
  1. O(N)

The first for loop takes N and the second also takes N so

O(N) = N + N = 2N = N

  1. O(N^2) The first for loop takes N and the second also N, but in this case it is nested. inner loop takes N for every other loop of outer loop

    O(N) = N * N = O(N^2)

  2. O(N)

The first for loop it takes N and the second also 5, but it is nested so

O(N) = 5 * N = 5N = O(N)

  1. O(log(N))

    to divide a number N by 2 continuously until it reaches 1, it takes log(N)

The Scientific Method
  • 2,374
  • 2
  • 14
  • 25