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?