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
1 answer
38 views

Find the value of return variable based on the value of n?

...
barnyard9's user avatar
1 vote
0 answers
9 views

Confusion on the use of the chain-rule for the total derivative of the NLL Loss function

So my question is about when we want to find the total derivative of the NLL Loss function $L$ w.r.t. $w_i$. So the "pipeline" is often expressed as: $$\frac{\partial L}{\partial w_i} = \...
ZenPyro's user avatar
  • 23
-1 votes
1 answer
45 views

Mergesort time complexity

Using the regular mergesort algorithm for a list, say $a[1...n]$, we call the merge function to merge, mergesort($a[1...\lfloor \frac{n}{2} \rfloor]$) and mergesort($a[\lfloor{\frac{n}{2}}\rfloor+1......
GaloisTH's user avatar
0 votes
0 answers
31 views

Dynamic Program to find well formed set in a rooted tree

You are given a rooted tree $T=(V,E)$ with $n$ nodes and the root $r$. Each node $u\in V$ has an integer label $l(u)$. Suppose $S⊆V$ then $S$ is well-formed if for every $u,v\in S$ if $u$ is an ...
Sooraj S's user avatar
  • 139
0 votes
2 answers
32 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: ...
john doe's user avatar
  • 167
1 vote
1 answer
47 views

Time complexity of algorithm with three loops and if statement

Suppose I have this c++ code: ...
john doe's user avatar
  • 167
0 votes
0 answers
17 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 ...
Shisui's user avatar
  • 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 ...
tbhaxor's user avatar
  • 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 ...
tbhaxor's user avatar
  • 128
2 votes
2 answers
112 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$ ...
Hugh Mann's user avatar
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, ...
petrit.vidishiqi's user avatar
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 ...
Mason Rashford's user avatar
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 ...
Mason Rashford's user avatar
1 vote
2 answers
146 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 ...
Mason Rashford's user avatar
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 ...
Josh Tint's user avatar
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 ...
dezdichado's user avatar
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, ...
Hugh Mann's user avatar
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, ...
Hugh Mann's user avatar
2 votes
1 answer
109 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. ...
Akash Ram's user avatar
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: ...
user163191's user avatar
0 votes
1 answer
59 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 ...
Hugh Mann's user avatar
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 ...
KSI's user avatar
  • 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 ...
user19121278's user avatar
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 ...
Jane's user avatar
  • 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 ...
Pole_Star's user avatar
  • 129
0 votes
2 answers
126 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....
C.C.'s user avatar
  • 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 ...
user129393192's user avatar
0 votes
1 answer
201 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 ...
Tejas Anand's user avatar
2 votes
1 answer
150 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 ...
Daviid's user avatar
  • 123
0 votes
1 answer
24 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) ...
Algo's user avatar
  • 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 ...
SpaceNugget's user avatar
0 votes
1 answer
51 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? ...
jon doyle's user avatar
0 votes
1 answer
59 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{...
user51462's user avatar
  • 123
2 votes
2 answers
67 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 ...
user51462's user avatar
  • 123
1 vote
1 answer
98 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 ...
TheCollegeStudent's user avatar
0 votes
2 answers
53 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 ...
user51462's user avatar
  • 123
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. ...
Mario Carneiro's user avatar
0 votes
0 answers
34 views

Shell sort algorithm analysis

Given this Shell sorting algorithm implementation: ...
Kim's user avatar
  • 1
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 ...
asdf's user avatar
  • 237
0 votes
0 answers
23 views

Shell algorithm knuth sequence time complexity analysis

Given this shell sort algorithm implementation: ...
Kim's user avatar
  • 1
0 votes
1 answer
72 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 ...
Ally Zane's user avatar
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,...
second_and_third_breakfast's user avatar
0 votes
0 answers
43 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 ...
TheCollegeStudent's user avatar
0 votes
1 answer
61 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}$ ...
EvaMGG's user avatar
  • 167
0 votes
0 answers
40 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 \...
Doc Stories's user avatar
-1 votes
1 answer
80 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 ...
Jip Helsen's user avatar
1 vote
1 answer
136 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 ...
TheCollegeStudent's user avatar
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 ...
Karan Mehta's user avatar
0 votes
1 answer
67 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 ...
Samiddha 's user avatar
-4 votes
2 answers
59 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 ...
Arushka's user avatar

1
2 3 4 5
40