Questions tagged [runtime-analysis]
Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.
981
questions
1
vote
1
answer
32
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.
...
- 11
0
votes
1
answer
52
views
Time Complexity for the given algorithm
Recently, I had to implement the following algorithm (similarly). Code in Kotlin:
...
- 101
0
votes
0
answers
37
views
Dijkstra's runtime analysis in terms of $|V|$ and $|E|$
I'm unsure as to the amount of operations in Dijkstra's shortest path in terms of $|V|$ and $|E|$.
My guess is that there are (worst case - complete graph):
$$|V| + \sum^{|V|}_{i=1}{(|V|-i)} = \frac{|...
1
vote
2
answers
111
views
Is the complexity of this two-sum binary search algorithm $O(\lg n)$ or $O((\lg n)^2)$?
This algorithm solves the Two-Sum problem$^1$ assuming that the input array/list is sorted.
...
- 115
0
votes
0
answers
60
views
Big O notation for halving substrings in a string of length n
I am trying to do some runtime analysis on a problem, but get stuck on some details.
I have a string $P$ of length $n$, where I am allowed to halve substrings inside of it and keep the right-hand side ...
1
vote
0
answers
44
views
Search algorithm with at most a constant $k$ failed accesses [duplicate]
Let $A$ be an array sorted in non-increasing order. Let $m$ be a natural number. For example, let $m = 10$. We want to find the index $i$ such that $A[:i]$ contain elements less than or equal to $m$, ...
0
votes
1
answer
32
views
Interpreting the time complexity of a program from function
$T(n)=5T(n/3)+n^2$ Consider this to be the running time of a program. How could we interpret
then numbers 5 and 3.
My Thoughts:
5 times will mean that the problem is divided into 5 subproblems each of ...
- 23
4
votes
0
answers
33
views
Polynomial multiplication in finite field without smooth-order roots of unity
I am working in a finite prime field $\mathbb{F}_p$ that does not have primitive $n$-th roots of unity for any large smooth integer $n$, which makes FFTs a bit difficult.
If I need to compute a ...
- 53
2
votes
3
answers
124
views
Find the smallest difference between two numbers in a DS in O(1) time
I got an assignment to create a new data structure, with the following rules:
Init - O(1).
Insert x - O(log$_2$n).
Delete x - O(log$_2$n).
Search for x- O(log$_2$n).
Find max difference between two ...
- 23
1
vote
1
answer
80
views
How to find parameter sets for a big-O expression to be fixed-parameter tractable?
I've been stuck on the following assignment taken from Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis:
Imagine that the following big-O expressions ...
- 13
3
votes
2
answers
302
views
Find an upper bound for T(n) = T(n/2) + T(n/2 + 1) using the Substitution Method base case fails
Given the algorithm
MYSTERY-ALG(n >= 0)
1 if n < 3 then
2 return 1
3 else
4 return MYSTERY-ALG(n/2) + MYSTERY-ALG((n/2) + 1)
I defined a recurrence
$ ...
- 45
1
vote
1
answer
63
views
Time Complexity of Exponentiation Operation as per RAM Model of Computation
Now, $\color{blue}{\text{Exponentiation}}$ is defined as
Exponentiation is a mathematical operation, written as $b^n$, involving two numbers, the base $b$ and the exponent or power $n$, and ...
- 231
1
vote
3
answers
58
views
Difference between an exact and Big O Notation for worst case runtime
I'm having a problem with an exercise, I'm supposed to calculate the exact worst case runtime and the worst case runtime in Big O Notation for a given algorithm.
This is what I'm struggling to ...
- 13
1
vote
0
answers
27
views
Worst case lower bound of the general number guessing problem
I have the following problem:
Let Alice and Bob be two people playing games.
Alice and only Alice owns a special device, Robo, that is capable of generating one truly random number $k \in \mathbb{N}$ ...
0
votes
0
answers
26
views
The total number of nodes and the height of a ternary search tree
So I need to insert into the ternary search tree (TST) about N strings. Each string is a unique ID "consists of 10 letters, the first 3 are upper case letters and the last 7 are digits" for ...
0
votes
0
answers
16
views
How do you analyze the asymptotic complexity of a recursive operation?
I have a decent intuition for spotting linear and quadratic complexity for iterative routines, but for ones with a recursive structure like the one below (or any other ones like routines performed on ...
- 271
2
votes
2
answers
625
views
Doubt about computing running time / time complexity of a function in Python
I am learning about time complexity now, and I am working with BST (Binary Search Trees).
This question needs some context and this is a follow up post to this post. Basically, I would like to compute ...
- 187
2
votes
1
answer
65
views
Find two very frequent items in a given array of comparable items
I am new to this community and I have a question regarding a problem I was trying to solve. Could anyone review my algorithm for solving this problem?
I want to emphasize also that the algorithm must ...
- 65
1
vote
1
answer
35
views
Product of sparse polynomials with FFT
I need to compute the product of two polynomials $f(X)$ and $g(X)$ over a finite field. The degrees of these polynomials are $n^2$ for some integer $n$. However, we also know that the polynomials are ...
- 53
1
vote
2
answers
81
views
How to use the step count method correctly for binary search?
I've tried to use the step counting method to get the worst-case time complexity for binary search. But I seem to mess it up, as my final result would be O(n) and ...
- 13
0
votes
0
answers
11
views
runtime of solving matrix differential equation wrt dimensions of matrix
Suppose a computer solves a coupled differential equations (with given boundary conditions) of which each equation deals with $2^n \times 2^n$ size of matrices as solutions. My question is
Does time-...
0
votes
1
answer
20
views
Complexity of unrolled loop in saxpy
I'm trying to calculate the complexity of the saxpy method, which aims to solve the equation $y=\alpha*x+y$, where $x$ and $y$, are vectors and $\alpha$ is a scalar.
There two versions of the ...
- 3
2
votes
1
answer
46
views
expected running time of Randomwalk for k-SAT
model: gambler ruin theorem.
A gambler has $i$ coins initially, in every step, he wins a coin with probability $p$, and loses a coin with probability $1-p$. The expected time that he loses all his ...
- 153
0
votes
0
answers
43
views
bellman ford and dijkstra sparse vs dense graphs
I believe using big o notation that Bellman-Ford is to be expected to be faster on sparse graphs and dijkstra's should be expected to be faster on dense graphs, but in practice dijkstra's is always ...
1
vote
1
answer
35
views
Why does sorting a collection have O(n log n) complexity?
Reading through https://developer.apple.com/documentation/swift/array/1688499-sort, it states "Complexity: O(n log n), where n is the length of the collection," but I don't have an intuition ...
- 13
1
vote
1
answer
50
views
3-colouring with a bounded amount of colors
The topic of 3-colouring is often talked about, but what happens if we limit the amount of times we can use one color? Take a graph $G=(V,E)$ with $k$ being the number of vertices, is it possible for ...
- 49
0
votes
0
answers
28
views
0
votes
1
answer
149
views
how many bits should I expect to flip, if I flip each bit with probability 1/n?
I am trying to work out some analysis for an algorithm I am trying to write, one step of what I am doing require knowing the answer to the above question.
I know it might sound a bit simple, but I am ...
- 298
0
votes
0
answers
17
views
Big O notation References and Resources
I am new to time complexity, and Big O notation. I have this question pertaining to this code in Python 3.X:
...
- 101
1
vote
1
answer
80
views
Time complexity of merging two lists while preserving order
I have two lists l1 and l2 of possibly unequal sizes (say, m and ...
- 11
1
vote
2
answers
26
views
How to count this operation for (int interval = n/2; interval > 0; interval /= 2) using counting primitive operation?
I was confused how to label this for (int interval = n/2; interval > 0; interval /= 2) with counting operation and estimating this operation
so that I can get ...
- 23
1
vote
0
answers
46
views
Plotting time-complexity vs actual run time
To my understanding, the time-complexity of an algorithm is a measure of its actual run time. For instance, an algorithm with a worst-case time-complexity $T(N)=$(constant)$\times N^2+$(lower order ...
- 11
0
votes
2
answers
22
views
solve the reccurence $\ T(n) = T(n-5) + \log n $
I tried to solve the following recurrence:
$\ T(n) = T(n-5) + \log(n) $ and $\ T(5) = 1 $
using iterative substitution:
$$\ T(n) = T(n-5) + \log(n) = \\T(n-10) + \log(n) + \log(n-5) = \\ T(n-15) + \...
- 155
0
votes
1
answer
16
views
Runtime of the following procedure
I want to calculate the runtime of the following code as a function of n:
...
- 155
1
vote
1
answer
30
views
Is "Mutation" Cheaper than "Calculating Derivatives"?
When it comes to optimizing objective functions belonging to Statistical and Machine Learning Models, there seems to be a general rule:
High dimensional objective functions with many parameters are &...
- 111
2
votes
1
answer
48
views
confusion about Hopcroft-Karp time complexity analysis
From Wikipedia:
"Each phase increases the length of the shortest augmenting path by at least one: the phase finds a maximal set of augmenting paths of the given length, so any remaining ...
- 23
3
votes
1
answer
103
views
Analytic combinatorics and less-precise running times
Analytic combinatorics and concrete mathematics are the mathematics of asymptotic counting, and they draw from combinatorics, analysis, and probability. These techniques have been applied to the ...
- 315
1
vote
0
answers
26
views
Big theta and big 0 bounds for iteration method and Master Theorem
In Algorithms 1, I'm noticing that big-Theta running times are always used for recurrence relations when using the iteration method. Meanwhile, using the Master Theorem always seems to result in a big-...
- 111
0
votes
1
answer
47
views
Solve the recurrence equation $T\left(n\right)\:=\:n\:+\:\sum _{i=1}^{n-1}\left(T\left(i\right)\right)$
I am trying to find the runtime of:
$T\left(n\right)\:=\:n\:+\:\sum _{i=1}^{n-1}\left(T\left(i\right)\right)$
$T(1)= 1$
What is the way to solve this kind of problems?
- 29
0
votes
1
answer
22
views
Define a directed edge in a DAG using partial ordering
I am trying to describe a novel type of DAG's construction algorithm. The directed edges of the graph corresponds to a partial ordering: i.e. any directed edge $e$ spanning from $f$ to $t$ also ...
- 131
1
vote
3
answers
126
views
Θ, O and Ω, and how they relate to each other as subsets
I am trying to understand how $\Theta(n)$, $O(n)$, and $\Omega(n)$ relate to each other as sets and want to make sure I'm on the right track.
I get that $Θ(n) \subseteq O(n)$ since $Θ(n)$ is stronger ...
- 11
0
votes
0
answers
19
views
NC with nearest neighbor gates
Consider a circuit belonging to the class $\text{NC}^i$, as defined here.
From my understanding, the circuit consists of AND, OR ar NOT gates, each of bounded fan in --- without loss of generality, ...
- 309
0
votes
0
answers
48
views
Time complexity of this for-loop
I know, the inner loop here is O(log n). But, I get confused by the multiplication in the outer loop part.
...
- 125
1
vote
1
answer
115
views
How many clock cycles are used to run my code?
Suppose that I want to know the number of the cycles of cpu clock that uses to run a specific code written with a specific programming language, like Python or others.
Can I do it?
I mean, do you have ...
2
votes
1
answer
43
views
Runtime analysis with multiple parameters: case study with heaps in Huffman coding
While studying a book on algorithms, I came across a question that asked about essentially $d$-ary Huffman coding, where the codeword alphabet has $d$ symbols (the usual case has $d=2$, with symbols $...
- 235
0
votes
0
answers
34
views
2D segment tree query time complexity
These sources cp-algorithms and geeksforgeeks
state that query complexity (for example, submatrix sum) of 2-D segment tree is O(logN * logM), because
it first descends the tree in the first ...
0
votes
1
answer
17
views
A high-level call-by-reference question
First, let $H$ be a graph represented as an array of adjacency lists say. Next, let FindDegree$(H,y)$ be a standard subroutine that takes $H$ and a vertex $y$ in $H$ as input, and that returns the ...
- 103
1
vote
1
answer
28
views
Solve recurrence where the base case's time complexity is a function of the original input size
I'm trying to analyse the time complexity of the following algorithm for generating the power set:
...
- 123
0
votes
0
answers
24
views
Intuition behind : recursive algorithm takes exponential time [duplicate]
So I am studying an introductory chapter to dynamic programming that suggests a general solution to an optimization problem that occurs straightforwardly from expressing the problem with a reccurence ...
- 201
1
vote
2
answers
54
views
Regularity condition for cases 1 & 2
My question concerns the version of the Master Theorem described in CLRS and in this handout.
I already understand the following:
If the regularity condition in case 3 does not hold, then we can't ...
- 11