Test #1 Review 3.3 #1– Mark Evertson

section 3.3 #1

This entry was posted in Uncategorized. Bookmark the permalink.

1 Response to Test #1 Review 3.3 #1– Mark Evertson

  1. Kate Poirier says:

    Hi Mark. You’ve got the correct big-O complexity, but your explanation isn’t quite correct. You’re right that there are 3 possible values of i. Similarly, there are 4 possible values of j. For a fixed pair (i,j), t is computed as t+ij. This means that for a fixed pair (i,j), there are two operations: one multiplication and one addition. So the total number of operations is 3 \cdot 4 \cdot 2 = 24, not 12. This is still a constant, so it’s O(1) as you said.

    It turns out that this constant is also \Theta(1). Almost the same proof that $24$ is O(1) shows that it’s also \Omega(1).

Leave a Reply

Your email address will not be published. Required fields are marked *