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.

Filter by
Sorted by
Tagged with
1
vote
1answer
27 views

Counting primitive operations on recursive functions

I'm reading Algorithm Design and Applications, by Michael T. Goodrich and Roberto Tamassia, published by Wiley. They teach the concept of primitive operations and how to count then in a given ...
2
votes
1answer
35 views

Understanding the upper bound proof for quick sort

I'm trying to understand the average run time of quicksort which is $O(n \log n)$. I understand the intuition behind it: if we partition array $A$ to e.g. $\alpha n $ and $(1-\alpha)n$ then we ...
0
votes
1answer
27 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
votes
0answers
12 views

Connected component- feature regions extraction

I'm trying to extract the connected component from a graph, in the following way: ...
1
vote
1answer
32 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 (...
1
vote
1answer
75 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 ...
1
vote
1answer
80 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 ...
0
votes
1answer
35 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 ...
0
votes
3answers
34 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 ...
0
votes
1answer
61 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
2answers
48 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
1answer
146 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
2answers
36 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
0answers
23 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
votes
1answer
84 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
1answer
59 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 ...
2
votes
2answers
125 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 ...
-1
votes
1answer
21 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.
-1
votes
2answers
53 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 ...
0
votes
2answers
52 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(nlgn)$$
-1
votes
2answers
27 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 ...
0
votes
1answer
20 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 &...
0
votes
1answer
35 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 ...
1
vote
1answer
85 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 (...
2
votes
2answers
70 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 $\...
1
vote
1answer
32 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 ...
0
votes
0answers
24 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?
0
votes
0answers
39 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. ...
1
vote
0answers
28 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 ...
0
votes
1answer
38 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 ...
1
vote
1answer
37 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 ...
1
vote
1answer
25 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. <...
1
vote
1answer
24 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 ...
0
votes
2answers
38 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*}...
0
votes
2answers
43 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 ...
-1
votes
1answer
15 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}
1
vote
1answer
46 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.
0
votes
0answers
19 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
1answer
75 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
1answer
117 views

Transitions between lexicographical orders

I have six characters: (,),[,],{,}. They are stored lexicographically: '(' < ')' < '[' < ']' < '{' < '}'. So I can store all balanced parenthesis sequences of length $n$ ...
1
vote
1answer
26 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
1answer
38 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} \...
1
vote
1answer
33 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: ...
3
votes
0answers
58 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 ...
1
vote
0answers
73 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 ...
0
votes
0answers
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
3answers
118 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 <...
0
votes
0answers
33 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} ...
1
vote
1answer
38 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 ...
0
votes
0answers
43 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 $\{...

1
2 3 4 5
37