New answers tagged time-complexity
0
votes
Time complexity for searching $k-th$ element from starting and ending of a linked list
It’s a trick question. Finding the k-th number takes O(k). Finding the 8-th item can be done in a constant number of steps so it takes O(1).
But with this kind of question, you are unlikely to do this ...
- 27.8k
0
votes
Time complexity for searching $k-th$ element from starting and ending of a linked list
Lets talk of each case one by one:
(FINDING FROM THE START)
SINCE QUESTION HAS ASKED US TO FIND THE ELEMENT FROM THE START AND HAS TO REACH PARTICULARY TO A PLACE THAT IS 8 TH FROM THE START . ...
3
votes
What is the time complexity of this algorithm of finding all prime numbers?
The following complexity is not tight; however closeby:
The complexity of the algorithm is at least $\Omega(n \sqrt{n}/\log^2 n)$ and at most $O(n \sqrt{n}/\log n)$.
For any natural number $x$, the ...
- 5,276
0
votes
Finding growth rate of T(n) of a code segment
Let $I$ be the number of times the for i is executed, $J$ the number of times for j, and $K$ the number of times ...
- 15k
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 $...
- 15k
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
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 ...
0
votes
Time complexity of GPU computing
From wikipedia
Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm
It doesn't take into consideration the computing capabilities of the ...
- 1,018
0
votes
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.♦
- 154k
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, ...
- 326
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 ...
- 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 ...
- 27.4k
0
votes
Time Complexity of Linear Search vs Brute Force
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$...
- 101
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 ...
- 21
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 ...
- 456
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 ...
- 27.4k
Top 50 recent answers are included