14 votes

Time Complexity of Linear Search vs Brute Force

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 ...
Steven's user avatar
  • 27.4k
7 votes

Time Complexity of Linear Search vs Brute Force

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 ...
NaturalLogZ's user avatar
5 votes
Accepted

Is there a faster algorithm than FFT if interested only on the maximum amplitude frequency?

Partial FFT and Sparse FFT can exploit an expected range of said maximum. Practically, the range of frequencies over which the maximum may occur is often known. There are also approaches to estimate ...
OverLordGoldDragon's user avatar
3 votes
Accepted

Are integer linear *feasibility* problems NP-hard?

Feasibility of integer linear programming (ILP) is also NP-hard. (Why? See https://cs.stackexchange.com/a/29916/755, Is 0-1 integer linear programming NP-hard when $c^T$ is the all-ones vector?, ...
D.W.'s user avatar
  • 154k
2 votes
Accepted

T(n) = T(n-1) + T(n-1) vs T(n) = 2*T(n-1)

Yes, the running time of the first is $\Theta(2^n)$ unless you have tail-call optimization or you do memoization. The running time of the second is $\Theta(n)$. Beware that the input size is actually $...
Pål GD's user avatar
  • 15k
2 votes
Accepted

Are there situations where we can decrease the time complexity of a program by increasing its ordinal complexity?

Okay, as discussed in the comments, I will be assuming that the programming language has something like a "break" statement, which completely skips all the remaining iterations of a loop, ...
Сергей Макеев's user avatar
2 votes

Time Complexity of Linear Search vs Brute Force

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 ...
Darren Clark's user avatar
2 votes
Accepted

Time complexity of a convergent series

For every sufficiently large $n$ (here $n \ge 1$ suffices), $T(n)$ is both lower bounded by a positive constant (e.g., $1$) and upper bounded by another positive constant (e.g., $\pi^2/6$). Therefore ...
Steven's user avatar
  • 27.4k
1 vote
Accepted

Time complexity of function

First observe $q(n)$ always returns either $0$ or $1$. This can be proven formally by induction. If $n \le 0$ this is immediate. If $n=1$ then the return value is $q(q(0)) = 1-q(0) = 1$. Suppose now ...
Steven's user avatar
  • 27.4k
1 vote

How to maintain completely dynamic convex hull quickly?

You can use my code. I implemented the ideas from the paper by Overmars and van Leeuwen. https://github.com/sumeetshirgure/DynamicPlanarHull/tree/master
Sumeet Shirgure's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible