Test #1 Review 3.3 #1– Mark Evertson

Posted on March 6, 2016 by MarkE

This entry was posted in Uncategorized. Bookmark the permalink.

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

Kate Poirier says:

March 7, 2016 at 3:44 pm

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)$ .

Reply

Leave a Reply to Kate Poirier Cancel reply

The OpenLab at City Tech:A place to learn, work, and share

The OpenLab is an open-source, digital platform designed to support teaching and learning at City Tech (New York City College of Technology), and to promote student and faculty engagement in the intellectual and social life of the college community.

top

The OpenLab at City Tech:A place to learn, work, and share

The OpenLab is an open-source, digital platform designed to support teaching and learning at City Tech (New York City College of Technology), and to promote student and faculty engagement in the intellectual and social life of the college community.