Welcome to the Treehouse Community
The Treehouse Community is a meeting place for developers, designers, and programmers of all backgrounds and skill levels to get support. Collaborate here on code errors or bugs that you need feedback on, or asking for an extra set of eyes on your latest project. Join thousands of Treehouse students and alumni in the community today. (Note: Only Treehouse students can comment or ask questions, but non-students are welcome to browse our conversations.)
Looking to learn something new?
Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and a supportive community. Start your free trial today.
Locker combination example... isn't this linear time?
How is stepping through possible locker combination numbers 00-99 different than guessing a number 1-100? The video says the locker example is exponential, but it seems the same as sequentially guessing in the linear-time counting example, i.e. 99999 would take 100000 guesses in the worst case (starting with 00000), right?
Balazs Peak46,121 Points
- 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.
David Lin35,864 Points
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.
Boban Talevski24,793 Points
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.