Skip to main content

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
0 votes
0 answers
13 views

Why is the time complexity of bidirectional breadth first search still considered O(V + E)?

I understand that if the branching factor of the graph is b and distance of goal vertex from source is d, then the time complexity is O(b^d). I also understand why that would be O(b^d/2) using ...
Shisui's user avatar
  • 121
1 vote
2 answers
44 views

What does "computer steps" mean in this runtime definition?

My algorithms textbook defines $T(n)$ as "the number of computer steps needed to compute fib1(n)" (where fib1(n) ...
Princess Mia's user avatar
0 votes
1 answer
22 views

How is the prefix function (for KMP) time complexity O(N)?

I'm looking at the algorithm for the prefix function from here https://cp-algorithms.com/string/prefix-function.html : ...
JobHunter69's user avatar
0 votes
1 answer
37 views

Is the Partition problem polynomial when all integers are large?

In the Partition problem, there are $n$ positive integers, and the problem is to decide whether they can be partitioned into two subsets with an equal sum. If all integers are "small" (at ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
42 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
-2 votes
2 answers
57 views

Precise definition of a brute force algorithm

What is the precise definition of a brute force algorithm? Is it one that simply has non-polynomial runtime?
Geremia's user avatar
  • 154
-2 votes
1 answer
49 views

The Hydra Game runs forever

I saw this question here: The Hydra Game algorithm I am also running into troubles with the same problem. I also learned of the problem in this Numberphile video, and also tried to compute it myself. ...
Lee's user avatar
  • 1
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
0 answers
12 views

Relation between running time of Insertion sort and number of inversions

What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer. Consider Insertion sort ...
Omkar's user avatar
  • 1
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
4 votes
2 answers
33 views

Run-time complexity of solving a system of integer linear equations

Given an integer $n$-by-$n$ matrix $A$ and an integer $n$-by-$1$ vector $b$, what is the run-time complexity of finding an integer solution $x$ to the system $A x = b$? In general, integer linear ...
Erel Segal-Halevi's user avatar
1 vote
2 answers
34 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
30 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
86 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
282 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
0 votes
0 answers
41 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
25 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
54 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
779 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
57 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: ...
ten_to_tenth's user avatar
1 vote
0 answers
28 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
40 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
92 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
57 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
  • 286
0 votes
2 answers
220 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
  • 159
0 votes
1 answer
60 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
87 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,684
0 votes
2 answers
95 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
64 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
85 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
56 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
45 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
117 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
1 answer
42 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
59 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
46 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
61 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
65 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
37 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
555 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
191 views

search for the next prime number more efficiently?

...
ant0982's user avatar
  • 13

1
2 3 4 5
21