Lecture Date: Monday, April 13
Okay, computer scientists! I’ve got two new algorithms for you! Let’s see if we can code them up and figure out what the complexity is!
I call them
Here’s the pseudocode for
1 2 3
We can even do
1 2 3 4 5 6 7 8
There’s a slight problem with this algorithm. Every time we delete something from the list, all the indices change… so if we are looking for a particular index, this doesn’t work. If we are looking for a particular item from the list, it works fine.
What’s the complexity of these two searching algorithms? How do we know? Can we code them up?
Let’s take a look at
1 2 3
How about this one? What’s the complexity? How can we code it up? How long will it take to run?