principleModerate
Time Complexity of Linear Search vs Brute Force
Viewed 0 times
linearforcesearchtimebrutecomplexity
Problem
I am currently watching the FreeCodeCamp Algorithms and Data Structures Tutorial. In the explanation for exponential time complexity, they explain that using a brute force attack on a combination lock would create O(x^n) time complexity. I am confused as this attack sounds very similar to a linear search of the passcode, going one by one until you find the right combination.
The confusion comes when you find that while brute force has a time complexity of O(x^n), linear search only has a time complexity of O(n). This therefore means that, depending on what you call the algorithm, the same instructions can have differing time complexities, which makes no sense.
Can someone explain whether FreeCodeCamp have made an error in the course or I am mistaken?
Thanks :)
The confusion comes when you find that while brute force has a time complexity of O(x^n), linear search only has a time complexity of O(n). This therefore means that, depending on what you call the algorithm, the same instructions can have differing time complexities, which makes no sense.
Can someone explain whether FreeCodeCamp have made an error in the course or I am mistaken?
Thanks :)
Solution
Time complexity is expressed as a function of some parameter, which is usually the size of the input.
The combination lock is not a perfect analogy as it is not immediately clear what the input would be. This confusion goes away once you deal with formally specified computational problems.
However, say that you want to express the time worst-case complexity of brute-forcing combination lock with $n$ dials, each of which can be in one of $x$ positions, where a single combination can be tested in constant time. Then the problem can be solved in time $\Theta(x^n)$.
The above time complexity is in $\Omega(x^n)$ since any algorithm needs to try each of the $x^n$ combinations in the worst case, and it is in $O(x^n)$ since there is an algorithm that takes time $O(x^n)$ to test all these combinations (this is not immediately obvious since you need to account for the time needed to generate the next combination to try from the current one, but it can be done).
If you are measuring the time complexity with respect to the number $N$ of all possible combinations, then it would be $\Theta(N)$, although this is somewhat less natural.
The combination lock is not a perfect analogy as it is not immediately clear what the input would be. This confusion goes away once you deal with formally specified computational problems.
However, say that you want to express the time worst-case complexity of brute-forcing combination lock with $n$ dials, each of which can be in one of $x$ positions, where a single combination can be tested in constant time. Then the problem can be solved in time $\Theta(x^n)$.
The above time complexity is in $\Omega(x^n)$ since any algorithm needs to try each of the $x^n$ combinations in the worst case, and it is in $O(x^n)$ since there is an algorithm that takes time $O(x^n)$ to test all these combinations (this is not immediately obvious since you need to account for the time needed to generate the next combination to try from the current one, but it can be done).
If you are measuring the time complexity with respect to the number $N$ of all possible combinations, then it would be $\Theta(N)$, although this is somewhat less natural.
Context
StackExchange Computer Science Q#162001, answer score: 14
Revisions (0)
No revisions yet.