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.
1,990
questions
0
votes
2
answers
27
views
Time complexity of algorithm involving function calls
Me again.
This time I have a more general question.
Suppose I have the following code snippet:
...
- 167
1
vote
1
answer
40
views
Time complexity of algorithm with three loops and if statement
Suppose I have this c++ code:
...
- 167
0
votes
0
answers
16
views
Runtime of randomization algorithm to find majority element in an array?
This is for the leetcode problem 169. Majority Element. Given an array of numbers, where there is a guarantee that there is a number that exists in the array greater than floor(n/2), one can find such ...
- 111
0
votes
1
answer
34
views
Why is the push operation in incrementally grown array stack is $O(n^2)$
This is from the Narasimha's data structure book
For nth element (n - 1 index), if we want to push an element, create a new array of size n and copy old array to the new, and at the end assign the ...
- 128
0
votes
1
answer
32
views
Explaination of incremental push's amortized time
In the Narasimha's data structure book, there is a line
The amortized time of a push operation in the incremental growth of array stack (realloc on every push) is $O(n) [O(n^2) / n]$.
I am confused ...
- 128
2
votes
2
answers
108
views
A $O(|E||V|)$ algorithm to determine if a graph is singly connected?
In exercise 22.3-13 of CLRS (Intro to Algorithms 3rd edition), the authors provide the following problem:
A directed graph $G = (V, E)$ is singly connected if the existence of a path from $u$ to $v$ ...
- 67
0
votes
1
answer
37
views
Solving Recurrence Relations with induction
We got the following tasks in our Higher Algorithm class, to repeat our proof techniques from class:
Find asymptotic upper bounds (as sharp as possible) for $T(n)$ in each of the following cases,
...
0
votes
2
answers
45
views
Prove $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})=\Theta(n\log^2{n})$ using induction
Please first take a brief look at my previous question. Here I want to do something similar but for $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})$. I know the answer is $T(n)=\Theta(n\log^2{n})$ and I want ...
- 151
0
votes
1
answer
34
views
find $f(n)$ for recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})=\Theta(f(n))$
We have recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})$ and
assume $T(1)$ is a constant. Find asymptotically tight bounds
$\Theta(f(n))$ for $T(n)$.
There's something that confuses me. We ...
- 151
1
vote
2
answers
141
views
Prove $T(n)=10T(\frac{n}{3})+n\sqrt{n}=\Theta(n^{\lg_3{10}})$ using induction
We have this recurrence: $$T(n)=10T(\frac{n}{3})+n\sqrt{n}.$$
We can solve it using Master Theorem and say it is
$\Theta(n^{\log_3{10}})$. I want to prove it using induction but I don't
know the ...
- 151
0
votes
0
answers
15
views
Semantically Compare Programs by Similarity?
In NLP, it's common to study the semantic similarity between pieces of text, which can be calculated in a number of ways. Are there any tools, methods, algorithms or processes that can be used to ...
- 13
0
votes
0
answers
26
views
Optimal algorithm to select unique values from a daily-growing list
Suppose I have a list of numbers, say $L$, that grows every day when a new batch of numbers get added to it every night. Right now, say the list is of size $M$, with the daily batch size is of the ...
- 101
0
votes
0
answers
54
views
Question about implication in proof that predecessor subgraph is a breadth-first tree
Given the following theorem and definitions from Introduction to Algorithms 3rd edition by CLRS:
Theorem 22.5: (Correctness of breadth-first search)
Let $G = (V, E)$ be a directed or undirected graph, ...
- 67
1
vote
1
answer
196
views
Question about step in proof that predecessor subgraph forms a breadth-first tree
Given the following theorem and definitions from Introduction to Algorithms 3rd edition by CLRS:
Theorem 22.5: (Correctness of breadth-first search)
Let $G = (V, E)$ be a directed or undirected graph, ...
- 67
2
votes
1
answer
107
views
What is the time complexity of this algorithm of finding all prime numbers?
I came up with this algorithm for finding all prime numbers from 1 to n. This algorithm could already exist, if it does I don't know what it is called.
...
- 31
1
vote
2
answers
38
views
Finding growth rate of T(n) of a code segment
I am presented with the following code segment and asked to find the growth rate, which can be done by finding the number of times the variable sum is incremented:
...
- 11
0
votes
1
answer
57
views
Is a predecessor subgraph always connected?
Given an undirected graph $G$ with non-negative edge weights, how can we prove that the predecessor subgraph $G_{p}$ of $G$ is always connected?
Here's how the predecessor subgraph is defined: for a ...
- 67
1
vote
0
answers
20
views
Why must a safe configuration be reached in `n^2 + n` rounds in Dijkstra's Self-stabilizing mutual exclusion algorithm?
In the book Self-Stabilization (Dolev, 2000) the author provides a proof (p.19) of Dijkstra's self-stabilizing mutual exclusion algorithm. An excerpt of the book showing the proof is found below.
At ...
- 11
0
votes
0
answers
28
views
Finding an algorithm EF[1,1] and PO division for more than two agents
From this research paper I want to write an algorithm for finding envy-freeness(EF) and Pareto optimality(PO) division for more than two agents.
We consider the problem of fairly and efficiently ...
- 501
0
votes
1
answer
35
views
Proving asymptotic classes
I am trying to teach myself asymptotic notations. I feel like I'm in over my head. I read the explanations in the text book, and Khan Academy. But when I try to do proofs, I can't grasp anything.
I'm ...
- 1
0
votes
0
answers
8
views
The Multi-Room Muddy Forehead Puzzle with Varied Color Perception
Imagine there are n children, and they are divided into three separate rooms (Room A, Room B, Room C) without knowing how many children are in each room. As before, their foreheads are marked with ...
- 129
0
votes
2
answers
123
views
Minimum number of comparisons to find $2$nd smallest element
Show that the second smallest of $n$ elements can be found with $n+\lceil\lg n\rceil-2$
comparisons in the worst case. (Hint: Also find the smallest element.) [1]
I tried but I have no idea how to, e....
- 129
0
votes
0
answers
41
views
finding the length of the GCD of two strings
Let's say you have two strings: a and b with GCD c. Why is it that ...
- 171
0
votes
1
answer
195
views
Proving the correctness of a greedy algorithm for the Circular Scheduling Problem
Consider the following variation on the Interval Scheduling Problem
You have a processor that can operate 24 hours a day, every day. People
submit requests to run daily jobs on the processor. Each ...
2
votes
1
answer
141
views
Ways to speed up a Recursive Backtracking Algorithm
When dealing with a Recursive Backtracking Algorithm what are the ways to speed it up and what computational hardware is involved?
I'm assuming from ignorance that everything is done by the CPU so the ...
- 123
0
votes
1
answer
21
views
How branching factor affects complexity of Monte Carlo Tree Search?
I was reading: https://stackoverflow.com/questions/34724201/whats-the-time-complexity-of-monte-carlo-tree-search
Where it says:
The runtime of the algorithm can be simply be computed as O(mkI/C)
...
- 1
1
vote
1
answer
60
views
Proving a greedy algorithm of finding MINIMAL group
I am given a group $A$ of real numbers and I have to find the minimal group $B$ such that for each $a$ in $A$ there exists at least one $b$ in $B$ such that $|a-b|\leq 1$
So what I think the algorithm ...
- 13
0
votes
1
answer
50
views
Parallel Algorithm Analysis: Loops
I have come across what seems to be a collapsed loop.
parallel-for i, j = 1...n
What would be the work and span/depth/critical path length be of loops like this? ...
- 11
0
votes
1
answer
58
views
Substitution method for the upper bound of a recurrence without an explicit base case
Pages 90-91 of 'Introduction to Algorithms' (4th ed.) show how the substitution method can be used for determining the upper bound on the recurrence:
$$T(n) = 2T(\lfloor n/2 \rfloor) + \Theta(n) \tag{...
- 113
1
vote
2
answers
63
views
Justification for the properties of algorithmic recurrences in 'Introduction to Algorithms' (CLRS, 4e)
The fourth edition of 'Introduction to Algorithms' defines algorithmic recurrences on page 77 as follows:
**Algorithmic recurrences
[...] A recurrence is algorithmic, if for every sufficiently large ...
- 113
1
vote
1
answer
92
views
First-Fit-Decreasing algorithm packs items of size at most 1 into bins of capacity 2
Consider the bin packing problem where we are given item sizes $a_1,\dots, a_n \in (0, 1)$, and all bins have capacity 2. The task is to pack the items in as few bins as possible, such that the total ...
0
votes
2
answers
51
views
Clarification of divide-and-conquer recurrence explanation in 'Introduction to Algorithms' (CLRS)
The following excerpt is from page 39 of the 4th edition of 'Introduction to Algorithms' (emphasis added):
2.3.2 Analyzing divide-and-conquer algorithms
[...]
A recurrence for the running time of a ...
- 113
5
votes
0
answers
75
views
Completeness of red-black tree operations
Red-black trees are defined to have the following invariants:
The nodes are in sorted order (it is a binary search tree).
The root is black, and leaves are black.
Every red node has black children.
...
- 531
0
votes
0
answers
34
views
1
vote
0
answers
18
views
Algorithm for finding relative estimate from absolute estimate
I am trying to find a textbook reference for an algorithm that gives you a relative estimate of a quantity $a$ (i.e. $|a-\overline{a}|\leq \epsilon_{rel} a$) from an algorithm that gives you an ...
- 237
0
votes
0
answers
23
views
Shell algorithm knuth sequence time complexity analysis
Given this shell sort algorithm implementation:
...
- 1
0
votes
1
answer
71
views
How to cover elements with minimum amount of elements
I'm trying to create a game but I am having some difficulties in coming up with a suitable algorithm for my problem.
I have elements from 1 to n and I am trying to cover all of the elements using the ...
- 11
0
votes
1
answer
33
views
Is there a non bruteforce apporach to solving a "synergistic knapsack"?
Sorry for making up a name for the thing, the main reason for posting this question is that I can't find out the name of the problem that i'm thinking about.
I was messing around with min/max DP stuff,...
0
votes
0
answers
41
views
Hardness of the bin packing problem
I have been reading up on the bin packing problem. In the bin packing problem, we are given $n$ items with sizes $a_1,a_2,\dots, a_n$ such that
$$
1 > a_1 \geq a_2 \geq \dots \geq a_n > 0
$$
The ...
0
votes
1
answer
60
views
Number of steps of binary search given a stopping criterion
Reading a paper, I have found an algorithm that uses binary search to find a number between $0$ and $n\in\mathbb{N}$. The stopping criterion for this binary search is that $t_2-t_1<\frac{1}{k^2}$ ...
- 167
0
votes
0
answers
39
views
Envy-Free Allocation is NP-Hard
If we consider the class fair division problem where we have a set of $n$-agents and a set $M$ of $m$-items, where each agent has a valuation function defined on the set of items $$v_i : 2^m \...
- 31
-1
votes
1
answer
77
views
SAT polynomial time
Hi I understood it is not currently possible to solve SAT in polynomial time. Does this mean we can not currently solve an expression with n different boolean variables or with m different symbols in ...
- 103
1
vote
1
answer
130
views
Chistofides' algorithm for the traveling salesman problem with relaxed triangle inequality
It is known that Christofides’ algorithm returns a 3/2-approximation for the traveling salesman problem given a complete graph $G$ such that distances obey the triangle inequality. Suppose that we ...
18
votes
4
answers
2k
views
Measuring time complexity in the length of the input v/s in the magnitude of the input
I know that formally the time compliexity of an algorithm is measured in the length of the input, which in binary would be the number of bits required to encode the input.
The problem that I have with ...
- 183
0
votes
1
answer
66
views
How to derive time complexity of the Recurrence Relation - T(n,m) = T(n-1,m) + T(n,m-1) + c
I know that, T(n,m) = T(n-1,m) + T(n,m-1) + c it's the recurrence equation of Longest Common Subsequence algorithm. And the time complexity of the LCS in case of recursive method is O(2^n+m).
The base ...
- 1
-4
votes
2
answers
57
views
Design and analyze an efficient algorithm that, given n distinct integers, returns an element which is neither the smallest nor the largest
I'm trying to prepare for mock exam, could you please help me with possible solutions?
Design and analyze an efficient algorithm that, given n distinct integers, returns
an element which is neither ...
- 1
1
vote
1
answer
56
views
The value of $r$, with $r≤ b$, that minimizes the expression $(b/r)(n+2^r)$ in the analysis of the radix-sort algorithm
In chapter 8 of the book "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein, lemma 8.4 is proved. (my question is after the proof of the lemma)
Given $n$ $b$-bit numbers ...
- 121
1
vote
0
answers
30
views
What is "crossover probability" in optimization techniques?
I am new to optimization methods. What is the meaning of "crossover probability" in optimization methods? I was reading the following lines from an article that this question came into my ...
- 111
0
votes
1
answer
87
views
What recurrence describes the time complexity of this algorithm?
The problem is as follows:
The input is an array $A$ of $n$ natural numbers such that:
(1) if the maximum occurs in $A[p]$ for an index $p$, then $$A[1] \leq \ldots \leq A[p-1] \leq A[p]$$ and $$A[p] ...
- 103
0
votes
1
answer
59
views
Prove that the problem MATCH is NP-complete
The problem MATCHED is defined as follows: given an infinite set S of strings of arbitrary length over the alphabet {0, 1}, determine if there exists a character of length n over the alphabet {0, 1} ...
