# 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
Filter by
Sorted by
Tagged with
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: ...
1 vote
40 views

### Time complexity of algorithm with three loops and if statement

Suppose I have this c++ code: ...
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 ...
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 ...
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 ...
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$ ...
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, ...
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 ...
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 ...
1 vote
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 ...
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 ...
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 ...
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, ...
1 vote
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, ...
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. ...
1 vote
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: ...
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 ...
1 vote
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 ...
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 ...
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 ...
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 ...
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.)  I tried but I have no idea how to, e....
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 ...
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 ...
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 ...
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 vote
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 ...
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? ...
58 views

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 ...
1 vote
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 ...
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 ...
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 ...
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 vote
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 ...
1 vote
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 ...
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 \leq \ldots \leq A[p-1] \leq A[p]$$ and A[p] ...