Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
0 votes
1 answer
15 views

How to count primitive Operations

ive been struggling with counting primitive operations. I know that you do not have to outline every operation that happens in your pseudocode but this is never the less a bit complicated for me. ...
lennuuu's user avatar
0 votes
0 answers
18 views

Time complexity of optimal index

Consider a data structure that stores a set of $n$ objects, where each object is a map of arbitrary key-value pair. The data structure maintains a reverse lookup table, where for each key-value pair, ...
SOFe's user avatar
  • 133
1 vote
1 answer
38 views

Algorithms by Dasgupta-Papadimitriou-Vazirani Prologue confusion

We will see in Chapter 1 that the addition of two n-bit numbers takes time roughly proportional to n; this is not too hard to understand if you think back to the gradeschool procedure for addition, ...
Bob Marley's user avatar
-1 votes
0 answers
32 views

Algorithmically determine if another algorithm is brute force?

Is there a way to algorithmically determine if another algorithm is a brute force algorithm? Can a Turing machine be programmed to do this? related: "Precise definition of a brute force algorithm&...
Geremia's user avatar
  • 152
0 votes
1 answer
28 views

Why is it impossible to do a linear time radix sort on n integers and ranging from $0$ to $n^{3} - 1$?

I propose by doing a base-n expansion of the numbers, we have that since there are $n^{3}$ values and $n$ digits in this expansion, there are a total of $\log_{n} n^{3} = 3$ digits. Note in this base-...
cdknight's user avatar
  • 103
0 votes
1 answer
26 views

Set partitions and integer partitions

Consider an algorithm that takes the input a finite set $X$ and an integer partition $\sum_{i=1}^k n_i=|X|$ and gives output all the set partitions $\left(S_1,\ldots, S_k\right)$ of $S$ satisfying $|...
rr314's user avatar
  • 101
0 votes
1 answer
29 views

How far can we push "counting argument" for proving lower bounds of time complexity?

It's obvious that we cannot find min (or max) in an array of length n in strictly less than n "steps". It's also well-...
e.gryaznov's user avatar
0 votes
1 answer
32 views

Is this depth search correct (DFS) Shouldn't one act according to the LIFO principle?

Shouldn't we actually continue with C after A, thought a depth search, follows the LIFO principle, isn't C the last node added in this case and shouldn't we expand C before B?
test's user avatar
  • 1
-2 votes
1 answer
40 views

Proving a statement involving asymptotic notation

I need help with this question. If it’s possible to do this without limits, please show. Thanks. Q: If f(n) is Ω(n) and g(n) is O(n), then prove or disprove the following statement: f(n) is O(n)
anaya's user avatar
  • 1
0 votes
0 answers
22 views

Randomized weighted majority with rational weights

Consider the RWM online algorithm as defined in this Wikipedia article; this version is with multiplicative update. Let us assume that we define our weights as a fraction; that is, $w_i^t = 1 / (M_i^t+...
Mahyar's user avatar
  • 81
0 votes
0 answers
18 views

Analysis of Simon's Algorithm: Probability Expression for Matching Queries

The Simon's problem is that, given a function $f:\{0,1\}^n\to\{0,1\}^n$ such that, for all $x,y\{0,1\}^n$ t satisfies $$ f(x)=f(y)\text{ iff }x=y\oplus s $$ where $s\in \{0,1\}^n$, and the Simon's ...
Sooraj S's user avatar
  • 139
7 votes
1 answer
585 views

Possible Mistake in Skiena's Algorithm Design Manual

In Skiena's book Algorithm Design Manual, 3rd Edition, it is claimed on page 45 that $$ mn - m^2 + m \in \Omega(mn) $$ where $m,n \geq 0$ and $m \leq n$. I claim that this is in fact false, with the ...
Joshua's user avatar
  • 173
2 votes
0 answers
122 views

Find the longest northeast path in $O(n\log n)$ time

Given a set $Z$ of $n$ points $(p_1,p_2,p_3, \ldots,p_n)$. The coordinates of these points are arbitrary numbers and are unsorted. If they give me $s$ and $t$ to be two points in $Z$. A northeast path ...
coding's user avatar
  • 121
1 vote
1 answer
96 views

Quick sort with $K-1$ pivots

I was thinking about quicksort with multiple pivots and I came across this question. How can we efficiently implement a version of Quicksort where we choose $k−1$ pivots to partition an array of ...
Haaziq Jamal's user avatar
1 vote
1 answer
63 views

Find all the induced paths with a start vertex

Let $G$ be a graph and let $v$ be a vertex. Is there a polynomial algorithm for the following operation? Operation. Find all the induced paths in $G$ with first vertex $v$. Background This problem is ...
licheng's user avatar
  • 405
-2 votes
1 answer
87 views

Amortized cost for Stack Operations

In this problem we consider two stacks $A$ and $B$ manipulated using the following operations ($n$ denotes the size of $A$ and $m$ the size of $B$):   PushA($x$): Push element $x$ on stack $A$.   ...
Avin's user avatar
  • 1
2 votes
1 answer
24 views

Is bitonic sort order preserving on keys with the same value?

We are all familiar with Bitonic Sort. The computations are predetermined and data-independent. Let's say we have a table A = [ 1,3,2,5,6,3,3,21 ]. The output ...
Tolis M.'s user avatar
2 votes
1 answer
267 views

Prove the relation between space complexity and time complexity of the graph search which uses "the explored set"

I was referring to the textbook Artificial Intelligence: A modern approach 3rd by Stuart Russell and Peter Norvig. what to prove about the general "graph search": (Here I assume "within ...
An5Drama's user avatar
  • 203
1 vote
1 answer
65 views

Scheduling classes with lower and upper bounds on students and classes

I am struggling to solve the following excercise: Design an assignment of a group of n students to m classes. Student i should take a minimum of $l_i$, and a maximum of $u_i$ within a set C1 of ...
FarsoFracico's user avatar
1 vote
1 answer
83 views

Amortised cost - transferring tokens

I'm trying to solve a problem from one of the older exams. Question: There's an infinite, one-dimensional board, with fields numbered consecutively $\ldots, -2, -1, 0, 1, 2, \ldots$ A move in the ...
Michał's user avatar
  • 113
1 vote
1 answer
180 views

Number of stops during trip - Dynamic programming algorithm

I am attending a course about algorithm design, and I have found an old test which has once been submitted. However, I don't have the solutions to it, and I am having some trouble with one specific ...
FarsoFracico's user avatar
2 votes
1 answer
392 views

Prove that the number of comparisons between elements in binary heap build is at most (2n-2)

Question Prove that the number of comparisons between elements in binary heap build is at most $2n-2$. $n$ is the total number of the nodes. Pseudocode ...
Lior's user avatar
  • 143
0 votes
1 answer
38 views

Does the Master Theorem apply to T(n) = 3T(n/3) + n/log2(n)?

Id say this is the first case of Master Theorem, but when I try to prove that the limit of f(n)/ n ^ (1-E) is 0, I cannot do it. Does anyone have a solution?
Mara F's user avatar
  • 1
4 votes
2 answers
777 views

What is the name of this search algorithm?

I was thinking about an efficient binary search for unsorted arrays with $n$ entirely unique elements, and came up with something that probably already exists. Here's how it works: At each level of ...
ijustlovemath's user avatar
3 votes
0 answers
92 views

Proof about Existence of Stable Matching

I've read the stable matching chapter in Kleinberg and Tardos's Algorithm Design and was wondering how one can show whether a stable matching under a given set of constraints exists. K&T introduce ...
entangled_photon's user avatar
1 vote
1 answer
90 views

Running time of modified BFS algorithm to find shortest path in weighted DAG

While the shortest path can be calculated with $O(V+E)$ time over a weighted directed acyclic graph using topological sort, I wonder about the running time of the following BFS type algorithm I ...
wsz_fantasy's user avatar
2 votes
1 answer
33 views

Expected number of mistakes grows logarithmically in number of iterations - improving performance?

I am reading a paper (link) in which an algorithm proposes a solution $\hat{\mathbf x}^{(t)}$ in each iteration $t = 1, \dots, T$, and each time, learns the true solution $\mathbf x^{(t)}$, so we ...
caitlin's user avatar
  • 21
2 votes
1 answer
46 views

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

...
Team B.I's user avatar
  • 263
1 vote
0 answers
11 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
51 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
34 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
80 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
  • 177
1 vote
1 answer
196 views

Time complexity of algorithm with three loops and if statement

Suppose I have this c++ code: ...
john doe's user avatar
  • 177
1 vote
0 answers
27 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
  • 121
0 votes
2 answers
74 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
  • 208
0 votes
1 answer
37 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
  • 208
2 votes
2 answers
160 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
1 vote
1 answer
61 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
52 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
38 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
181 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
18 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
53 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
59 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
252 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
184 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
41 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
79 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
24 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
32 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 ...
A. H.'s user avatar
  • 498

1
2 3 4 5
41