Hi ashish and Hamster,
First of all, thank you so much for your posts. They are very much
appreciated.
Hamster, you mentioned that to show that an algorithm is O(2^n), I need
to show that there is some other function (say f or g) that looks
exactly the same. Thats where I lost you. How is this h
Your calculation looks OK, you're on the right track there.
For part C... "big-oh" notation means the worst case running time. Note
that you probably should think of it as ( x * 2^n ) + ( y * n^2 ) where
x and y are constants. To show that is O(2^n) you need to show that the
worst case is still O
2^n is exponential, it grows way faster than n^2 which is polynomial.
So asymptotically, limit n^2/2^n tends to zero so n^2 loses its
contribution as n grows.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algori
I don't know if I'm on the right track, perhaps someone can give me
some pointers. Thanks.
1b) Since algorithm A is of O(2n^3), and it can solve a problem of size
n = 20 in one
hr, then by substituting n = 20 into the equation, we have that A
performs
2 * (20 ^ 3) = 16000 operations in 1 hr.
t
