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
2 answers
31 views

Can a Code Script be Optimized for Time and Space Complexity Using Logic Gates

let's say that I have a Python script that performs various operations, including data manipulation, conditional logic, and iteration. However, I'm concerned about its time and space complexity ...
edge selcuk's user avatar
0 votes
1 answer
18 views

$F(n, L) = 2F(n / 2, L) + nL + n^2 log(n)$ and Master Theorem

I have the following recurrence: $F(n, L) = 2F(n / 2, L) + nL + n^2 log(n)$. Am I correct in saying that $F(n, L) \in O(n \log(n) L + n^2 log(n))$? I got to this result by bounding the $nL$ and $n^2 \...
Jovan Komatovic's user avatar
1 vote
2 answers
72 views

Bound $T$ asymptotically tight | Recursive trees

Let $\alpha \in (0, 1),\space l \geq 2$ and $T: \mathbb{N}\rightarrow\mathbb{R}^+$ such that, $T(n) = \begin{cases} n^l + T(\alpha n) + T((1-\alpha)n) & : n > 1 \\1 : n=1 \end{cases}$ Bound $...
X4J's user avatar
  • 113
2 votes
1 answer
252 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
0 votes
0 answers
38 views

Calculating Runtime Complexity: Recursion + Memoization vs Dynamic Programming (with example)

For cases where recursion is used as well as memoization (so that a number of subtrees of what would otherwise be the overall recursive call tree are each replaced to be ...
mishar's user avatar
  • 101
1 vote
0 answers
21 views

Clustering 2D points with flavour

Problem Description I have two sets of 2D points with flavours: Noisy points $$p_i = (x_i, y_i, f_i) : p_i \in N : |N|\approx 10^8 $$ and true points $$p_{t_i} = (x_{t_i}, y_{t_i}, f_{t_i}) : p_{t_i} \...
Emil Jansson's user avatar
0 votes
1 answer
53 views

Time Complexity: Determining if a binary tree is balanced

I found an algorithm for determining if a binary tree is height-balanced. It Gets the height of left and right subtrees using dfs traversal. Return true if the difference between heights is not more ...
Ali Naseri's user avatar
4 votes
2 answers
773 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
1 vote
1 answer
45 views

How to prove the time complexity of a function without calculating the precise number of steps taken? (Example: cost of optimal binary search tree)

This is my dynamic programming solution in Python to the problem of finding the cost of the optimal binary search tree: ...
ideals_go's user avatar
  • 113
1 vote
0 answers
26 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
1 answer
39 views

How are pointers modeled on bit-based computer models?

Why bit-based computer models? The perhaps most commonly used computer model is a random access machine that can store natural (or even real) numbers in infinitely many cells indexed by natural ...
KGM's user avatar
  • 103
0 votes
1 answer
85 views

Prove with potential method that dynamic table with $q > 1$ expansion runs in amortized constant time

Suppose I have a dynamic table supporting $Insert$ procedure, which sets an input value after the tail of the dynamic table. If the underlying table is already full, we multiply its size by $q > 1$....
coderodde's user avatar
2 votes
1 answer
246 views

An efficient way to find a pair of unrelated edges

I'm writing a program which uses an undirected graph to represent certain social connections, and I'm trying to check whether or not it's contains a specific induced subgraph. Given a dense an ...
Benicio Agüero's user avatar
1 vote
0 answers
56 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
39 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
181 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
  • 149
0 votes
1 answer
58 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
74 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,600
0 votes
2 answers
89 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
  • 109
1 vote
1 answer
41 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
  • 11
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
1 vote
1 answer
71 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
29 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
55 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
43 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
97 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
214 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
41 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
55 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-)...
proof-of-correctness'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
42 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
55 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
40 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
62 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
34 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
483 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
  • 187
0 votes
0 answers
52 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
167 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
39 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
  • 532
2 votes
1 answer
72 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
39 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
85 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
131 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
56 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
162 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
41 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
  • 127
0 votes
2 answers
81 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
2 3 4 5
21