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)... IE that there is some function that looks exactly the same (just with different values for x and y), that gives a larger result for all values of n as n tends to infinity.
In other words, you can show 4n^2 + 3 is O(n^2) by showing that 5n^2 (or 6n^2, or 7n^2, or...) is greater than it for all values of n. Now, if they use the word "prove" rather than "show" you will need to do more work, (possibly along the lines of recurrences, Master Theorem, etc.) so read the question carefully... Good luck! Disclaimer: I am a former lecturer in algorithms. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
