5
$\begingroup$

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 :)

Improve this question
$\endgroup$
13
  • 3
    $\begingroup$ Hint: what are the definitions of x and n, and are they the same in both cases? $\endgroup$
    – Jörg W Mittag
    Commented Sep 13, 2023 at 5:39
  • 8
    $\begingroup$ The trick is to define what "x" and "n" mean before you start making claims like "the complexity is O(x^n)" or "The complexity is O(n)". If the number of digits on the lock is n and there are x possibilities for each digit, then the complexity of bruteforce is O(x^n). If the number of possible passwords is N, then the complexity of linear search is O(N). Obviously N = x^n. Your confusion rose from using the same symbol "n" to refer both to the number of digits, and the number of passwords. From now on I suggest you use different symbols when referring to different quantities. $\endgroup$
    – Stef
    Commented Sep 14, 2023 at 8:23
  • 1
    $\begingroup$ Apart from comparing abstract time complexities (e.g. "O(n^2) is slower than O(log(n)) for large enough inputs"), this is why I completely abstain from the O(n) terminology. Bubblesort is O(n) for a clever-enough definition of n. It's a few more characters, but much more clear to say that brute forcing a combination lock is O(alphabet.size^digit_count). Then these sorts of questions just disappear $\endgroup$
    – Alexander
    Commented Sep 15, 2023 at 2:26
  • 2
    $\begingroup$ @Alexander: One of the few languages which actually specifies algorithmic complexity for certain operations in the language specification (more precisely, the library specification), is C++. Interestingly, they try to avoid Bachmann-Landau notation as much as possible and rather specify the exact number of operations allowed. For example, the complexity of std::partial_sort is defined like this: "Approximately (last-first)log(middle-first) applications of cmp." Where last, first, middle, and cmp are the parameters of the function. No Oh, Omega, Omicron, or Theta in sight. Also, no N. $\endgroup$
    – Jörg W Mittag
    Commented Sep 15, 2023 at 23:02
  • 2
    $\begingroup$ std::sort does use Big-Oh, and does use N, but at least, it explicitly and clearly defines what, exactly, N is: "O(N·log(N)) comparisons, where N is std::distance(first, last)." They also clearly define what operations they are counting, namely comparisons. $\endgroup$
    – Jörg W Mittag
    Commented Sep 15, 2023 at 23:04

5 Answers 5

Reset to default
14
$\begingroup$

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.

Improve this answer
$\endgroup$
7
$\begingroup$

You are absolutely right that they are the same algorithm! At least, in this context. "Brute-force attack" is a general term referring to finding a solution to the problem at hand by trying every possibility. Linear-search usually refers to a more specific case where you are scanning through a specified, arbitrarily ordered set (like an array) and looking for a specific value. But you are correct that a "brute-force attack" is just a linear-search through the set of possible solutions according to some ordering.

The discrepancy comes from the variables meaning different things in these contexts. When talking about linear-search, we usually use $n$ to represent the size of the set we are searching through. But in the context of a combination lock, they are using $n$ to represent the length of the passcode (and $x$ to be the number of values each "digit" can take.) Thus the set of all possible passcodes is actually of size $x^n$ and the analysis of linear search agrees that this will have a worse-case runtime of $O(x^n)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So if I was to linear search the padlock, would that mean the time complexity is also 𝑂(𝑥𝑛)? $\endgroup$
    – jacoboneill2000
    Commented Sep 13, 2023 at 19:12
  • $\begingroup$ @jacoboneill2000 yes. $\endgroup$
    – NaturalLogZ
    Commented Sep 13, 2023 at 19:13
4
$\begingroup$

It's all about what you call $n$.

If $n$ denotes the length of the key, then the complexity can be exponential $O(a^n)$.

If $n$ denotes the number of combinations that can be tried, obviously $O(n)$. But given that $n=a^l$ where $l$ is the key length, that is still $O(a^l)$.

Other example:

Ordinary matrix product takes $O(n^3)$ operations for $n\times n$ matrices. But only $O(n\sqrt n)$ for matrices of $n$ elements.

Improve this answer
$\endgroup$
3
  • $\begingroup$ What is the difference between the length of the key compared to the number of combinations? Not trying to be pedantic I genuinely want to learn. $\endgroup$
    – jacoboneill2000
    Commented Sep 15, 2023 at 10:28
  • $\begingroup$ @jacoboneill2000: which term don't you understand ? $\endgroup$
    – user16034
    Commented Sep 15, 2023 at 11:40
  • $\begingroup$ @jacoboneill2000 as an example, a combination lock with two symbol alphabet and key of length 3 has 8 possible combinations. Adding a 4th position to the key doubles the number of combinations (the search space) to 16. $\endgroup$
    – Alexander
    Commented Sep 15, 2023 at 12:10
2
$\begingroup$

They are both correct, but the N is different.

Algorithmic brute force: Inputs: X: Size of each combination element N: Number of combination elements Algorithm generates all possible combinations and tries each one. Algorithm is O(X^N)

Linear brute force: Inputs: N: List of all possible combinations Algorithm tries each item in list Algorithm is O(N)

but N here is the same as X^N from the other, and would probably be generated in O(X^N) time itself.

Improve this answer
$\endgroup$
0
$\begingroup$

Linear search runs in linear time $O(n)$ where $n$ is the input size. For example, if you add one item to the array, one extra step is needed.

Brute-force attacks need linear time $O(n)$, but here, $n$ is the value, because the value does not index an array. Therefore, to increase the memory usage in constant steps, you need to add a bit to brute-force. Adding a bit doubles the steps. This is called Pseudo-polynomial time.

Improve this answer
$\endgroup$
1
  • $\begingroup$ As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Commented Sep 17, 2023 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.