Big Oh Exercise

Question 1

Using Big Oh notation, indicate the time requirement of each of the following tasks in the worst case. Describe any assumptions that you make.

• After arriving at a party, you shake hands with each person there.
• Each person in a room shakes hands with everyone else in the room.
• You climb a flight of stairs.

Question 2

By using the definition of Big Oh, show that

• 6n² + 3 is O(n²)

• n² + 17n + 1 is O(n²)

• 5n³ + 100n² - n - 10 is O(n³)

• 3n² + 2ⁿ is O(2ⁿ)