Questions tagged [algorithm-analysis]
Questions about the science and art of determining properties of algorithms, often including correctness, runtime and space usage. Use the [runtime-analysis] tag for questions about the runtime of algorithms.
2,022
questions
2
votes
1
answer
38
views
Proof for Gas Refills on Circular Route Problem
The circular route gas station problem asks: If given a car with an unlimited gas tank, find the gas station on a circular road that if started from would allow you to travel station to station ...
- 23
1
vote
2
answers
53
views
What does "computer steps" mean in this runtime definition?
My algorithms textbook defines $T(n)$ as "the number of computer steps needed to compute fib1(n)" (where fib1(n) ...
- 111
0
votes
1
answer
33
views
Is repeated function evaluation constant-time if the function is defined by the entry?
In an algorithm, given a natural number $n$, i have to calculate all integer entries of a function $f_n:R_n\to\mathbb{R}$ within an interval $R_n=[a,b]$ in the real line. Clearly, this amounts to ...
0
votes
0
answers
31
views
Closed-form for exact number of iterations of binary search
Consider a sorted list of $n$ elements $x_1, \ldots, x_n$. Using binary search to find $x_k$ in this list takes $f(n, k)$ iterations, where $f : \mathbb{N}^2 \to \mathbb{N}$ is a function such that, ...
- 103
0
votes
1
answer
72
views
How to count primitive Operations
ive been struggling with counting primitive operations. I know that you do not have to outline every operation that happens in your pseudocode but this is never the less a bit complicated for me. ...
- 9
0
votes
0
answers
20
views
Time complexity of optimal index
Consider a data structure that stores a set of $n$ objects, where each object is a map of arbitrary key-value pair.
The data structure maintains a reverse lookup table, where for each key-value pair, ...
- 133
1
vote
1
answer
43
views
Algorithms by Dasgupta-Papadimitriou-Vazirani Prologue confusion
We will see in Chapter 1 that the addition of two n-bit numbers takes time roughly
proportional to n; this is not too hard to understand if you think back to the gradeschool procedure for addition, ...
- 111
0
votes
1
answer
30
views
Why is it impossible to do a linear time radix sort on n integers and ranging from $0$ to $n^{3} - 1$?
I propose by doing a base-n expansion of the numbers, we have that since there are $n^{3}$ values and $n$ digits in this expansion, there are a total of $\log_{n} n^{3} = 3$ digits. Note in this base-...
- 103
0
votes
1
answer
26
views
Set partitions and integer partitions
Consider an algorithm that takes the input a finite set $X$ and an integer partition $\sum_{i=1}^k n_i=|X|$ and gives output all the set partitions $\left(S_1,\ldots, S_k\right)$ of $S$ satisfying $|...
- 101
0
votes
1
answer
30
views
How far can we push "counting argument" for proving lower bounds of time complexity?
It's obvious that we cannot find min (or max) in an array of length n in strictly less than n "steps". It's also well-...
0
votes
1
answer
33
views
Is this depth search correct (DFS) Shouldn't one act according to the LIFO principle?
Shouldn't we actually continue with C after A, thought a depth search, follows the LIFO principle, isn't C the last node added in this case and shouldn't we expand C before B?
- 1
-2
votes
1
answer
40
views
Proving a statement involving asymptotic notation
I need help with this question. If it’s possible to do this without limits, please show. Thanks.
Q: If f(n) is Ω(n) and g(n) is O(n), then prove or disprove the following statement: f(n) is O(n)
- 1
0
votes
0
answers
22
views
Randomized weighted majority with rational weights
Consider the RWM online algorithm
as defined in this Wikipedia article;
this version is with multiplicative update.
Let us assume that we define our weights
as a fraction;
that is, $w_i^t = 1 / (M_i^t+...
- 81
0
votes
0
answers
19
views
Analysis of Simon's Algorithm: Probability Expression for Matching Queries
The Simon's problem is that, given a function $f:\{0,1\}^n\to\{0,1\}^n$ such that, for all $x,y\{0,1\}^n$ t satisfies
$$
f(x)=f(y)\text{ iff }x=y\oplus s
$$
where $s\in \{0,1\}^n$, and the Simon's ...
- 139
7
votes
1
answer
589
views
Possible Mistake in Skiena's Algorithm Design Manual
In Skiena's book Algorithm Design Manual, 3rd Edition, it is claimed on page 45 that
$$
mn - m^2 + m \in \Omega(mn)
$$
where $m,n \geq 0$ and $m \leq n$. I claim that this is in fact false, with the ...
- 173