Question

1)If an algorithm performs N steps then we say it is O(N) ?

2) An example of something that is O(N) is(chose one)

A)printing to the screen.B)executing a conditional statement. C) initializing an integer variable. D) looping through an array of size N.

3)Suppose we found the run time of an algorithm was O(2N³ + 4N² + 5N + 3). What is the Big O notation for the algorithm?

A) O(5N), B) O(4N^2), C) O(N^3), D) O(2N^3)

Answer 1

PLEASE FIND THE ANSWER(S) and EXPLANATION BELOW.

          

1. If any algorithm takes N steps, then we say that it has O(N) (TRUE.)
   • O(f(n)) is nothing but the number of steps taken to run the code.\
   • Here f(n) takes N steps, hence it is O(N)
2. OPTION D
   • All the other like:
     • print data to screen takes a single step. O(1)
     • execute a conditional statement is also a single step. O(1)
     • Initializing an integer variable is also O(1)
     • looping through an array of size N. Hence, it is O(N)
3. OPTION C
   • 2N³ + 4N² + 5N + 3
   • <= 2N³ + 4N³ + 5N³ + 3N³
   • <=14N³
   • =O(N³)