Questions tagged [runtime-analysis]

Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.

Filter by
Sorted by
Tagged with
1 vote
0 answers
44 views

Computational complexity of an algorithm involving permutations

I'm interested in getting a precise estimate of the computational complexity of an algorithm I wrote involving permutations. Permutations are represented in my code as arrays of the integers $1$ ...
Matt Samuel's user avatar
0 votes
0 answers
35 views

Running time of variant of Dijkstra's algorithm

Consider the problem of finding the shortest-path distances from an origin vertex to all other vertices in a digraph. Normally in Dijkstra's algorithm, we visit the vertex whose shortest distance from ...
Andrew's user avatar
  • 287
0 votes
2 answers
61 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
1 answer
53 views

Optimizing findMissingNumber algorithm to O(N)

This problem is from Cracking the Code Interview: An array A contains all the integers from Oto n, except for one number which is missing. In this problem, we cannot access an entire integer in A ...
veron's user avatar
  • 1
0 votes
1 answer
37 views

Is it an open problem if CDCL algorithms violate SETH?

Strong Exponential Time Hypothesis states that general SAT, where clauses are not limited in length, can't be solved in time $o(2^n)$. It's proven that DPLL algorithm requires $\Omega(2^n)$ time in ...
rus9384's user avatar
  • 1,393
-1 votes
2 answers
63 views

Finding asymptotically tight upper bound of a recursion relation

Find an asymptotic tight upper bound for the following recursion relation: $$T(n)=5T(\frac{n}{5})+\log^2(n)$$ I tried to solve it by applying iteration: $$T(n)=5T(\frac{n}{5})+\log^2(n)=5(5T(\frac{n}{...
GBA's user avatar
  • 99
0 votes
1 answer
18 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
0 votes
0 answers
6 views

Asymptotics Accounting for Invocation Frequency in the Context of the broader system

I did some thinking and analysis this evening and I'm wondering if what I'm pointing out here is interesting: https://medium.com/@nwcodex/invocation-asymptotics-runtime-cost-based-on-the-anticipated-...
user161310's user avatar
0 votes
0 answers
39 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
0 answers
26 views

I/O Complexity Analysis with Memory Hierarchies

How to go about analysing the I/O complexity when there are multiple levels of memory involved? Looking up I/O complexity analyses returns papers such as this one, which generally assume for ...
William Edwardson's user avatar
2 votes
0 answers
52 views

Algorithm to compute sum of quotient polynomials

Let $f(X)$ be a polynomial in $\mathbb{F}_p[X]$ for some prime $p$ (of size 256 bits) that is not necessarily FFT-friendly. Let $a_1,\cdots,a_n$, $b_1,\cdots, b_n$ be $\mathbb{F}_p$ elements. What is ...
Mathdropout'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
1 vote
0 answers
34 views

What is the worst case time complexity of unranking n choose k combinations (combinatorial number system, combinadics)

The combinatorial number system shows that there is a bijection between the natural numbers less than $n \choose k$ and $n\choose k$ combinations. There is a greedy algorithm for unranking ...
Quantum Guy 123's user avatar
0 votes
3 answers
60 views

How do you stop an algorithm at a specific run time?

so I'm trying to write an algorithm in C to play the game of Reversi. I've already written in basic minimax algorithm yet I am not very satisfied with it. I want to implement alpha-beta pruning to my ...
Wolfking's user avatar
  • 101
0 votes
0 answers
72 views

Recurrence relation for TSP using recursion

This is a Python algorithm using recursion to solve Travelling Salesman Problem, consider $G$ a complete graph: ...
Hackerman's user avatar
  • 101
0 votes
1 answer
39 views

How do you calculate the amount of iterations the loop "for (i = 1; i < n^3; i += n)"

How do you calculate the amount of iterations the following loop will have in terms of n?: for (i = 1; i < n^3; i += n) { } I've gotten as far as: $$i=(x-1)...
user19843013's user avatar
0 votes
2 answers
51 views

Can a program that terminates have a running time of infinity? (Or not have an upper bound)

Can we have an algorithm that takes some input and does something random to it (in such a way that the algorithm does terminate) which does not have a worst-case running time upper-bound? A (non-)...
Ibrahim Hasaan's user avatar
0 votes
1 answer
41 views

A Problem with Solving a Recurrence relation

I Hope someone Can help me with that: $T(1)=2$ $T(n)=\left(T(\frac{n}{2})\right)^2\cdot2^n $ what is the runtime complexity of the algorithm (base 2) Thanks a Lot!
Bubi's user avatar
  • 1
-2 votes
1 answer
32 views

Solving a recurrence relation formula with squared

I hope someone can help me with that: $$T(n)=T(2^{\sqrt{\log n}})+1$$ I will be asked to answer what is the runtime complexity of the algorithm. I tried to set m=2^ and still failed.
Bubi's user avatar
  • 1
0 votes
2 answers
38 views

Dropping terms in proving the runtime for a recurrence?

I am trying to learn how to prove the runtime of a recurrence relation, particularly through induction. I was looking at this lecture PDF, and on the first page, the author writes this: Recurrence: $...
gorilla_glue's user avatar
-1 votes
2 answers
36 views

If we find that, e.g., T(n)<=d*n*lg(n) for some d that depends on n, is T(n)=o(nlgn)?

In the substitution method, if we find that, for instance, T(n) < dnlg(n) but only for some d that depends on n, then can we say that T(n) = o(nlg(n)) (little-oh) in some cases? For example, in ...
thebasqueinterdisciplinarian's user avatar
0 votes
2 answers
32 views

Function / Algorithm that take fixed time to compute

I was wondering if there are any mathematical functions or algorithms that take a known minimum amount of time to calculate. The closest thing I could find to this is Proof of Work algorithms used for ...
Anters Bear's user avatar
0 votes
1 answer
56 views

Is time complexity $O(n^{n/log(n)})$ considered subexponential time?

If there is an algorithm with time complexity $O(n^{n/log(n)})$, is that already exponential time or still subexponential time? It shouldn't be considered quasi-polynomial since the exponent is also ...
user avatar
0 votes
1 answer
33 views

How can it be formally proved that $f \in O(⌊f ⌋)$

I'm trying to prove that $f \in \mathcal{O}(\lfloor f \rfloor)$ given that $\forall m \in \mathbb{N}, f(m) \geq 1$ Here's what I've thought of so far, we can set C = 10 and k = 1 and somehow prove ...
Raghav Sinha's user avatar
1 vote
2 answers
359 views

Can dot producting the result of vector-matrix multiplication speed up the runtime?

Suppose we have a matrix $A$ of dimension $n \times n$ and two vectors $\vec{u}$ and $\vec{v}$ of dimension $n$. Then we have $A\vec{v} = \vec{x}$ with time complexity $O(n^2)$ and space complexity $O(...
yosmo78's user avatar
  • 177
0 votes
0 answers
51 views

I would not be able to get my simulation in my life time

I am running a simulation on my computer. I tried to multiply two polynomials $g(x), h(x)\in GF(2)[x]$, with $degree(g(x))= 8165$, and $degree(h(x))=25$. This multiplication took almost $20$ minutes ...
Robin Kurtz's user avatar
0 votes
1 answer
117 views

search for the next prime number more efficiently?

...
ant0982's user avatar
  • 13
0 votes
0 answers
68 views

What is the expected time complexity of this algorithm?

In the following algorithm $A[1..n]$ denotes an array $A$ of size $n$, of $n$ distinct integers. Func1() and Func2() are functions that run in $\mathcal O(\log n)$ and $\mathcal O(n)$ time, ...
Keio203's user avatar
  • 257
3 votes
0 answers
37 views

TSP algorithm with a good run-time based on properties of the graph (not just based on number of nodes/edges)?

In the worst case, the Traveling Salesperson Problem (TSP) is mostly accepted to take exponential runtime in terms of $|V|$ and $|E|$ (the number of vertices and edges respectively). But for many real-...
chausies's user avatar
  • 512
2 votes
1 answer
66 views

Complexity of right-to-left Knuth-Morris-Pratt algorithm

Suppose we modify the Knuth-Morris-Pratt string-matching algorithm to scan the pattern right-to-left a la Boyer-Moore, and consequently apply the shift rule on the right side of the cursor instead of ...
giofrida's user avatar
  • 183
0 votes
1 answer
36 views

What are the actual costs $c_i$ in the potential method?

In "Introduction to Algorithms" by Cormen et al. the Potential Method is explained. For example, we have the following representation for the amortized costs of the i-th operation with ...
P_Gate's user avatar
  • 103
0 votes
0 answers
82 views

Analysis of randomized algorithms

The expected running time, $T(n)$, of quicksort when the pivot is chosen uniformly at random satisfies $$ T(n) \leq \mathcal O(n) +\frac{1}{n}\sum^{n-1}_{i=0}(T(i) + T(n - i)),$$ which leads to the ...
Keio203's user avatar
  • 257
1 vote
1 answer
97 views

Show that $TIME(\sqrt{n})$ = $TIME(1)$

Also known as CMU 15-455, Spring 2017, Homework 2.4. Before I ask the main questions, let me first give a sketch of my idea. First, recall the definition of big-$O$ and time complexity class $TIME(t(n)...
Bedivere's user avatar
2 votes
1 answer
53 views

Sieve of Eratosthenes for factorization: bitwise complexity?

As is well-known (and easy to prove), carrying out a sieve of Eratosthenes on the first $N$ integers takes a number of word operations in the order of $N \sum_{p\leq \sqrt{N}} 1/p \sim N \log \log N$, ...
H A Helfgott's user avatar
1 vote
2 answers
161 views

How can we prove that "extract almost minimum" operation in a priority queue cannot be done in o(log n)?

Suppose we want to create a priority queue with 2 operations: insert and extract almost min. Extract almost min operation selects either the first minimum or a second minimum item from the structure ...
JsonResponse's user avatar
0 votes
0 answers
40 views

Runtime Analysis of Uniform Sampling via exact degree computation

Let $\mathcal{A} \subseteq \mathcal{B}$ given as a collection of arrays. The degree of an element $a \in \cup \mathcal{A}$, is the number of sets of $\mathcal{A}$ that it contains - that is, $d_{\...
Rma's user avatar
  • 123
0 votes
2 answers
54 views

Finding the runtime out of a recursion formula when using divide-and-conquer

In divide-and-conquer, one uses the following formula to find the runtime: $$T(n) = aT(n/b) + f(n).$$ I am confused with the meaning of the constants $a$ and $b$, as well as by the question of how to ...
user153448's user avatar
1 vote
2 answers
83 views

Average runtime random search without replacement

Consider an algorithm that is tasked with searching the array A. Let n be the size of the array, let i be a random number between 1 and n. Finally, k is the target object we are searching for. If A[i] ...
confuseddogman's user avatar
0 votes
1 answer
50 views

In the Master Theorem, if one term is smaller than another, can we drop it from the equation and use big O instead of theta?

Considering the runtime analysis (with the master theorem) of the function below $T(n) = 12T(\frac{n}{4}) + 2\sqrt{n} + \log^4(n)$. As I could not figure out a way to get the equation in the form $T(...
Mini's user avatar
  • 101
11 votes
3 answers
3k views

Is Big-Theta a more accurate description of worst case run time than Big-O?

Question I was asked: Does it make a difference if I say "The worst case run time is $O(n^2)$ vs the worst case run time is $\Theta(n^2)$?" To me, the only difference is that when we say $O(...
Carter Falkenberg's user avatar
-1 votes
1 answer
85 views

Help me solve recursion equation by using recursion tree method

Hello I am trying to solve this recurrence equation using the recursion tree method: T (n) = T (n −1) + n^2 In particular, what is big-O of T (n)? Here is what I have done so far: I am not sure if I ...
Mario's user avatar
  • 3
-3 votes
2 answers
50 views

Iterative solution of recurrence relation $T(n)=4T(\frac{n}{2})+\frac{n^3}{log_2n}$

Please help me to find the Time Complexity of the recurrence relation $T(n)=4T(\frac{n}{2})+\frac{n^3}{log_2n}$ using iterative method.
Xited's user avatar
  • 1
1 vote
0 answers
39 views

Probability that an Algorithm Deviates from Its Behaviour after Multiple Rewindings

I do have a seemingly fundamental question that I somehow struggle to intuitively make sense of. Setting: Let us consider a randomized algorithm $R$ that has $t$ steps. In each step, it is fed with ...
user153219's user avatar
1 vote
1 answer
74 views

Time complexity for finding the number of triangles in a graph

In our class we considered the problem written in the title. The below given time complexities where simply given, but not derived or explained. Therefore I tried myself to derive them, while I using ...
imbAF's user avatar
  • 185
1 vote
1 answer
91 views

Turing machine read time

Suppose I have a Turing machine that takes as input any string of length $n$, where $n$ is odd, and the Turing machine returns the middle character of the string. What time complexity class is this in?...
user918212's user avatar
0 votes
2 answers
38 views

Loops running time as function of n

Suppose I have the following code and I'd like to compute running time as function of $\ n$: ...
bm1125's user avatar
  • 157
1 vote
4 answers
152 views

What happens to the running time if we reduce the size of input?

Let there is an algorithm whose running time is $O(n^2)$. Suppose we apply a preprocessing step on the algorithm in $O(n)$ so that it reduces the input size to $O(\sqrt{n})$ but doesn't effect the ...
M a m a D's user avatar
  • 1,509
1 vote
0 answers
40 views

k-Circle Cover - How to show the faster algorithm isn't slower

I am having two algorithms, of which the second is a refinement of the first. However, I am having trouble to show that the seemingly better algorithm runs at least as fast as the first algorithm. The ...
Sudix's user avatar
  • 659
2 votes
1 answer
109 views

Runtime complexity of permutation function

I am trying to find the asymptotic run time complexity of the following function which will return a list of all permutations of nums. ...
user1234's user avatar
0 votes
1 answer
163 views

Time Complexity for the given algorithm

Recently, I had to implement the following algorithm (similarly). Code in Kotlin: ...
kaneda's user avatar
  • 101

1
2 3 4 5
21