If the worst case time complexity of an algorithm is(g(n)), what does that mean.
ID: 3612964 • Letter: I
Question
If the worst case time complexity of an algorithm is(g(n)), what does that mean. CLRLS gives an explanation on p46 that I don't understand. If the worst case is(g(n)), does that mean the worst case is also O(g(n))? Need to know the above for the following: givenalgorithms 1, 2, 3,4 with worst-case timecomplexity (n2),O(n), (log n), (n lg n), which one is the best touse? If the worst case time complexity of an algorithm is(g(n)), what does that mean. CLRLS gives an explanation on p46 that I don't understand. If the worst case is(g(n)), does that mean the worst case is also O(g(n))? Need to know the above for the following: givenalgorithms 1, 2, 3,4 with worst-case timecomplexity (n2),O(n), (log n), (n lg n), which one is the best touse?Explanation / Answer
The function g(n) is (f(n))iff there exists apositive real constant c and a positive integern0such that g(n) cf(n) for all n > n0.