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,948
questions
0
votes
1
answer
307
views
Understanding a summation notation. Sum(j=2 to n) j - 1
I have been reading analysis of insertion sort in the "Introduction to algorithms" and faced a problem with understanding a specific summation notation when the worst case occurs.
I know how ...
1
vote
1
answer
123
views
Proof of approximation ratio for approximate triangle inequality version of k-center
Consider the standard $k$-center problem i.e find $k$ disks of radius $r$ that cover all points in a point set $P$. This problem has a well known greedy 2-approximation algorithm where you (...
- 190
1
vote
1
answer
90
views
Why does it take O(n!) time to specify a canonical ordering for learning flatten adjacency matrices/graphs?
I was reading a paper for learning graphs (paper is GraphRNN) and it says in section 2.2 (emphasis by me):
Vector-representation based models. One naive approach would be to represent G by flattening ...
- 2,950
0
votes
1
answer
208
views
How to prove the my greedy algorithm for placing guards?
Given $n$ images placed in indexes $x_1 < x_2 < ... < x_n$ and an endless number of guards, where each guard if placed in index $y$ can protect $[y-0.5,y+1]$. I want to protect all images ...
- 13
0
votes
1
answer
283
views
an algorithm to find the shortest path between two vertices whose weight is divided by 3?
I am trying to think of an algorithm such that giving a graph $G(V,E)$, and a weight function $w\colon E \to \mathbb{N}_+$ (which means giving every edge in the graph a positive weight), and a source ...
- 3
0
votes
3
answers
109
views
Can the worst-case analysis of $f(n)$ be $\Omega(g(n))$ but not $O(g(n))$?
I am struggling to wrap my head around using $\Omega$-notation to describe worst-case running time of an algorithm, or $O$-notation to describe the best-case running time. Specifically, I struggle to ...
- 101
1
vote
3
answers
633
views
How to solve $T(n)=4T(\sqrt{n}/3)+(\log n)^2$ with the master theorem?
Can somebody help me with this recurrence please?
$T(n)=4T(\sqrt{n}/3)+(\log n)^2$
0
votes
3
answers
521
views
$(\log n)^{\log n}$ lower-bound and upper-bound
we know that $n \geq \log{n}$ however I understand that $(\log n)^{\log n}$ grows faster than $n$. I have been trying to prove this however I can't seem to figure it out.
4
votes
1
answer
184
views
Count Sketch probability bound
I have been reading up on the Count Sketch algorithm, and I stumpled upon the Count Sketh algorithm explained in section 5 of https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf. Then, I ...
2
votes
2
answers
183
views
Quicksort: Probability of an element being compared to fewer than $k$ pivot elements
Assume we want to use quicksort on some array $s$ with length $n$ consisting of only $n$ distinct elements.
Let $S_{(1)},S_{(2)},\dots,S_{(n)}$ be the sorted order of the elements in $S$.
Furthermore, ...
0
votes
0
answers
42
views
Recursive approach of longest common subsequence
I tried to solve Longest common subsequence problem using recursion, however as I later discovered, my thinking approach was wrong.
I took 2 strings say s1 and s2 with lengths l1 and l2, s1="...
- 1
-1
votes
1
answer
249
views
Proof of Correctness : Arranging the sheep
I've come across a question in Codeforces contest 719(Div - 3).
The problem goes like this :
I was able to solve the problem by using another approach but had to use 4*n auxiliary space, where n is ...
-1
votes
3
answers
846
views
recursive algorithm to sort children and parents based on value
Edit: I dont have CS background and I'm still studying Algorithms, so any help will count!
I met this algorithm while I was in interview, I didn't know what category it falls in, and hence I was ...
- 117
2
votes
2
answers
177
views
Sorting by repeated reversal
Let $A$ be an array of $n$ integers containing the numbers $\{1, 2, \dots , n\}$ in
some arbitrary order. For integers $i$ and $j$ such that $1 ≤ i < j ≤ n$, let
$\mathrm{Reverse}(A, i, j)$ be a ...
- 157
-1
votes
1
answer
24
views
How would the classes of regular, context-free, decidable, and Turing-recognizable languages relate to each other
I'm a bit confused as to how they relate to each other. I think I understand them individually but not sure how they would relate.
- 33
-1
votes
2
answers
903
views
sum of array with O(1)
I have an array of n elements. Smallest element that exists in the array is x and the largest element is x+n. None of the numbers between x to x + n is missing from the array. i need an algorithm to ...
- 1
0
votes
2
answers
123
views
How to show working for summing of Big O notation
The equation below is intuitively correct, but how do you show that this is actually the case? What is the working out needed?
$$\sum_{i=1}^{n-1}O(\lg n)=O(n\lg n)$$
- 113
-1
votes
2
answers
82
views
Undecidable or Decidable
In a typical data structures class, we look at a variety of problems: finding an element in a list,
sorting a list, balancing a binary search tree, finding the shortest paths in a graph, etc.
Would ...
- 33
0
votes
1
answer
74
views
What is the difference between designing an algorithm that solves a problem and creating a TM that decides a language?
Question: What is the difference between designing an algorithm that solves a problem and creating a Turing machine that decides a language?
A turing machine "decides" the language if it &...
- 33
0
votes
1
answer
146
views
Why do researchers only count the number of multiplications when analyse the time complexity of Matrix Multiplication?
In this article about the recent breakthough in Matrix Multiplication, it quotes Chris Umans's words:
Multiplications are everything. The exponent on the eventual running time is fully dependent only ...
- 632
0
votes
0
answers
367
views
Average number of comparisons for a successful search of a prime number in a binary search tree
A binary search tree is constructed by inserting the following value sequentially:
$$3, 9, 1, 6, 8, 7, 10, 4, 2, 5$$
Let $p_v$ be the probability to search for the value $v$ in the binary search tree (...
user135579
2
votes
2
answers
232
views
Big-O notation for lower bound instead of Big-Omega
In the Wikipedia's Binary search tree, one can read
Traversal requires $O(n)$ time, since it must visit every node.
Since it is question of a lower bound, shouldn't we write
Traversal requires $\...
- 123
1
vote
1
answer
42
views
Do the following two CFGs describe the same language
Do the following two CFGs describe the same language
S → aS | bS | ε
S → aS | Sb | ε
Would the answer to this be no, because the order can't be switched? bS and Sb are different. I'm a bit confused ...
- 33
0
votes
0
answers
42
views
How to know that the substrings 01 and 10 does not require an infinite amount of memory to count the substrings [duplicate]
Why does {w | w has equal number of 01 and 10 substrings} not require an infinite amount of memory
to “count” the number of 01 and 10 substrings?
- 33
0
votes
0
answers
72
views
Complexity of backtracking to find power set given random array of numbers
Given an array of elements which can contain duplicates, this is an algorithm that solves the problem.
...
- 23
1
vote
0
answers
31
views
Is there a branch of CS about studying function calls branching?
I know little about computer science. I wrote a function that has some ifs and may call itself recursively.
Is there a branch of computer science that studies these possible branches?
I'd like to ...
- 111
0
votes
1
answer
658
views
A visitor at a political convention with n delegates
So I have been asked to specifically construct a divide and conquer algorithm for the question:
"You are a visitor at a political convention with n delegates; each delegate is a ...
- 27
1
vote
1
answer
41
views
How would I prove that the regular expression rejects string?
Prove that the regular expression $\Sigma\Sigma(ab\cup ba)^∗a$ rejects the string $aabaabba$.
Would this be because the union of $ab$ and $ba$ would not accept the string $aabaabba$? I'm just confused ...
- 33
1
vote
1
answer
43
views
Number of Comparisons in an Algorithm
The number of comparisons in the following algorithm is supposed to be $3n/2 - 3/2$ if $S$ is odd. I understand that the for loop is $3n/2$ comparisons, but I fail to see where the $-3/2$ comes from.
<...
- 13
1
vote
1
answer
539
views
Finding a tight bound for a recurrence relation
Problem:
Give tight asymptotic bounds $( \Theta )$ for the following function:
$$ T(n) = T(n-2) + n $$
Answer:
We are not given the base case. I am going to assume that $T(0) = 0$ and $T(1) = 1$. Here ...
- 349
0
votes
2
answers
43
views
Finding a lower bound for the expression $\log(n!)$
Problem:
Is $\log(n!) \in$ $\Omega( n^n )$?
Answer:
Since $n! > n^n$ for all $n > 1$ we can conclude that: $\log(n!) \in$ $O( n^n )$.
Let us look at the special case where $n = 4$.
\begin{align*}...
- 349
0
votes
2
answers
46
views
Finding a lower bound for the expression $\ln^k(n)$
Problem:
Assume that $k \geq 1$ and $\epsilon \geq 0$, is $\ln^k(n) \in$ $\Omega( n^\epsilon)$?
Answer:
In the special case of $\epsilon = 0$, I claim the answer is no. I suspect the person who wrote ...
- 349
-1
votes
1
answer
44
views
Given the following state diagram, write out its formal definition as a 5-tuple
I got these for four of them, but I can't get the transition function.
Q = {q1, q2, q3, q4}
Σ = {a,b}
q1 is the start state, and
F = {q4}
- 33
1
vote
1
answer
183
views
Finite automata start state
Can a finite automata not have a start state?
I think it is possible for a finite automata to not have a start state. However, I'm not sure if I'm correct.
- 33
0
votes
0
answers
27
views
Recurrence relation of an algorithm
how can I know what are the recursive calls of this algorithm ?
in line two there are 2 recursive calls and I don't know how to write this as T(n) for the Recurrence relation.
Here is the algorithm :
1
vote
1
answer
214
views
Find minimum number of points which intersect overlapping arcs
Say I have a circle of a fixed radius, with overlapping arc intervals along its edge. I want to return a minimum set of Points which intersects all arcs in $n^2$ time.
I'm having some trouble proving ...
2
votes
1
answer
124
views
Transitions between lexicographical orders
I have six characters: (,),[,],{,}. They are stored lexicographically: '(' < ')' < '[' < ']' < '{' < '}'. So I can store all balanced parenthesis sequences of length $n$ ...
- 65
1
vote
1
answer
114
views
How to use Runge–Kutta methods in a second order ODE
Consider a second order equation $F=ma=m\ddot{x}$.
In the language of Euler's method
$\ddot{x}(t+dt)=F(t,x(t),\dot x(t))$
$\dot{x}(t+dt)=\dot x(t)+\ddot x(t)dt$
$x(t+dt)=x(t)+\dot x(t)dt$
Basically, ...
1
vote
2
answers
103
views
Solving $T(n) = 2T(\frac{n}{2}) + n\log(n)$ without master theorem
Solving $T(n) = 2T(\frac{n}{2}) + n\log(n)$ without master theorem, given $T(1) = 1$
My approach with recurrence tree:
$n \sim n\log(n)$
$\frac{n}{2} \sim 2 \frac{n}{2}\log(\frac{n}{2})$
$\frac{n}{4} \...
- 294
0
votes
1
answer
182
views
Average case analysis by key comparisons of Max Sort
I'm having trouble approaching this average case analysis in terms of key comparisons.
The pseudo-code is as follows:
...
5
votes
0
answers
424
views
How to find the Expected height of a randomly built binary tree
I would like to find out the Expected height of a binary tree where the insertions are based on a random function. I.e. for each node I visit, there is a $\frac{1}{2}$ probability of choosing right or ...
- 59
1
vote
0
answers
76
views
Can somebody please explain what are these variables doing here?
I have this algorithm:
I understand overall what's happening here, we're shrinking the blossoms (odd cycles) to end up with a bipartite matching problem, and then opening them again to get a maximum ...
- 121
0
votes
0
answers
19
views
Computer Science [duplicate]
I am trying to solve the following problem to find big-theta. I am having a lot of trouble, if anyone can help!
T(n)=8T(√n)+log^2(e^n)?
The logarithm is base 2 and is squared.
8
votes
3
answers
471
views
How can we find the number of pairs of intersecting ranges on a circular number line?
I recently thought of and managed to solve this algorithmic problem:
On a infinite 1-dimensional number line, we have N ranges specified by two distinct integers <...
- 425
0
votes
0
answers
67
views
substitution method - proving karatsuba algorithm is not O(n)
I want to prove that $T(n) \neq O(n)$ for the Karatsuba algorithm, which has the following recurrence:
$$ T(n) = \begin{cases} k_1, & \text{if $n$ = 1} \\
3T(n/2) + k_2n, & \text{if $n \gt$ 1} ...
- 101
1
vote
1
answer
131
views
Can someone help me fully grasp idea and time/space complexity with this code?
My understanding is the following:
Time = With the initial not state is just to check if there are no elements in the list a. This is done in O(1) time. The first ...
- 115
0
votes
0
answers
67
views
Counting number of sequences summing to target
This is a problem that I have been struggling to understand in a theoretical computer science book I've been reading:
We call a sequence of $n$ integers $x_1, \dots, x_n$ valid if each $x_i$ is in $\{...
0
votes
1
answer
161
views
For any DFS of a directed graph, is the strongly connected component containing the vertex with the lowest post order number also contains the sink?
I am stumped on the following question:
For any depth first search of a directed graph, is it true that the strongly connected component containing the vertex with the lowest post order number also ...
- 213
1
vote
0
answers
69
views
Experts problem with one perfect expert
This question concerns a variant of the 'experts' problem and the randomized weighted majority algorithm that can be used to solve it.
This is the description of the problem from Wikipedia:
Imagine ...
- 11
1
vote
1
answer
54
views
Towers of Hanoi with sufficiently many stacks, show that $T_k(n)=\Theta(n)$ for all $k\geq 2 + \frac{n-1}{2}$
I'm trying to show that for the following Towers of Hanoi general algorithm that $T_k(n)=\Theta(n)$ for all $k\geq 2 + \frac{n-1}{2}$, I'm not sure how to incorporate the restriction on $k$ into my ...