reset password
Author Message
G190852562
Posts: 162
Posted 14:17 Dec 08, 2014 |

5. Using "Big-Oh" notation give the worst case running times of the following algorithm as a function of n.

Function ( n )
for i ? 1 to n do
      for j ? 1 to 2 do
             x = x+1
 O(n)
 O(n^2)
 O(n lgn)
 O(lg n)
 
 I feel that the obvious answer for this question is the second option. But I feel that the first option can also be possible since the inner for loop is not iterating through n elements.
 
6. Suppose T(n), f(n) are non-negative real valued functions defined for all n>0

 T(n)= O(f(n)) if and only if there exist constants _______, n0 >= 0 such that ____________ for all _______

 c < 0 , T(n) <= c * f(n), n <= n0
 c < 0 , T(n) <= c * f(n), n >= n0
 c > 0 , T(n) <= c * f(n), n >= n0
 c < 0 , T(n) >= c * f(n), n <= n0
 c < 0 , T(n) >= c * f(n), n >= n0
 c > 0 , T(n) <= c * f(n), n <= n0
 c > 0 , T(n) >= c * f(n), n <= n0
 c > 0 , T(n) >= c * f(n), n >= n0
 
 Why is the last option the answer? Shouldn't it be T(n) >= f(n)/c?