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
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. ...
user avatar
0 votes
1 answer
52 views

Time Complexity for the given algorithm

Recently, I had to implement the following algorithm (similarly). Code in Kotlin: ...
user avatar
  • 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{|...
user avatar
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. ...
user avatar
  • 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 ...
user avatar
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$, ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 $ ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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}$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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-...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 49
0 votes
0 answers
28 views

Trying to count up time units of this pseudocode but unsure what to put for a specific line

...
user avatar
  • 185
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 ...
user avatar
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: ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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) + \...
user avatar
  • 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: ...
user avatar
  • 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 &...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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-...
user avatar
  • 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?
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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, ...
user avatar
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. ...
user avatar
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 ...
user avatar
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 $...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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: ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 11

1
2 3 4 5
20