Locker combination example... isn't this linear time?

• If you have 1 digit locker, n = 1. You have 10 possible variations for one digit, so that's 10^1 = 10.
• If you have 2 digit locker, n = 2. You have 10 possible variations for one digit, so that's 10^2 = 100.
• If you have 3 digit locker, n = 3. You have 10 possible variations for one digit, so that's 10^3 = 1000.

As you can see, you will go up exponentially. If you add one more digit, you get ten times more difficult complexity.

Dan,

Think of it this way:

The padlock problem would be linear if you could add just one number at a time to the list of possibilities. For example, if at first there is only 1 possibility (say, 0), and you add another possibility (say, 1), then you have 2 possibilities. Then add another (say, 2), and there's now 3 possibilities. And on and on. The problem is linear, since for each new number you add, the number of possibilities grows linearly (O(n), where n is the number of numbers you've added.).

However, in the padlock problem as presented in the video, you're adding 10 new possibilities at a time with each additional dial you add. For example, with one dial, you have 10 possibilities, and then after you add another dial, 10 more possibilities for each of the original 10 now exist, making the new number of possibilities 100. Add another dial, and now there are 1000 possibilities. And on and on ... with each new dial you add, there's 10 times more than the previous number of possibilities. This makes the problem exponential (O(10^n), where n is the number of dials you've added), not linear.

Hope that helps!

You are confused about picking the value of n. n does not equal 100 in the 2 digit locker combination, but rather n is equal to 2. Each time n increases in value, the time to guess expands exponentially.

Yes. 99999 would take 100000 guesses at the worst case. But it isn't linear. Note that 100000 = 10 ^ 5 (where 5 is n, the number of digits in the combination). Therefore it makes sense that time complexity is O(10 ^ n).

I hope this makes sense.

You should see n as the size of the input. The size of the input isn't 100 in the 2 dial locker example, it's 2. So, with the number of possible digits being 10 (this should be considered a fixed number for this particular problem), you get 10 to the power of 2 (or 100) attempts needed to crack the code. Or in general O(10^n) where n would be the number of dials which we consider as input.

So we have an algorithm to crack these padlocks and the number of attempts needed depending on the number of dials (remember this is the size of the input - n), is 10^n. So, for a number of dials being 2, we need 100 attempts, for 3 we need 1000 attempts and so on. So the number of attempts is increasing exponentially as the number of dials increases, which is why this is considered exponential time.

Same thing holds true for the password example explained later in the video. As you add a character to your password, you are making it exponentially harder for anyone to crack it, so the size of the input n is the number of characters in your password.