# Questions tagged [runtime-analysis]

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

939 questions
Filter by
Sorted by
Tagged with
17 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 ...
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 ...
18 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: ...
23 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 ...
35 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 ...
32 views

### Why is the time complexity of merge sort with a $\Theta(n^2)$ merge function $\Theta(n^2)$?

The original problem I was solving was what would the time complexity of a merge sort algorithm be, if it used a merge algorithm with complexity $\Theta(n^2)$ instead of $\Theta(n)$. The solution says ...
14 views

### Bubble Sort Runtime complexity analysis l [duplicate]

I'm trying to find the time complexity of this cod line by line can you help me?
18 views

### Karatsube-Ofman runtime complexity computation

I have a question and didn't understand the solution, since we didn't take how to do it in the lecture and it's not explained in the solution sample. Question: One can generalize the Karatsube-Ofman ...
21 views

### Insertion Sort running time calculating using summtion

I was reading Introduction to algorithms, and stopped at the calculating the running time. For each $j = 2,3,..,n$ where $n = A.length$, we let $t_j$ denote the number of times the while loop test in ...
31 views

### Time complexity when loop index is an exponent

For any $n$ and any $x$, if one implements a loop to calculate: $$\sum_{i=0}^n x^i$$ What is time complexity of said loop if we assume $x^i$ to have time complexity of $O(i)$? What confuses me is the ...
49 views

### N points with maximum sum distance

Given a distance matrix for 50,000 points, how do I select $N$ points so that the sum of all distances between the $N$ points is maximized? $N$ could be as high as 100. To calculate the sum of ...
47 views

### Optimal Word Guessing Algorithm in $O(n \log n)$

Say that your friend picks a word $(w_1, w_2,\dots,w_n)$ according to a known probability distribution $(p_1,p_2,\dots,p_n)$. You ask yes or no questions until you are certain which word has been ...
148 views

### What could be the most efficient algorithm to compare two unsorted arrays?

I have two arrays A and B of the same length n. I am looking to swap such that all the elements of array A are less than each element of B. Elements in A and B can be unsorted. Example Inputs: ...
33 views

### Randomized Quick Sort Discussion

I would just like to discuss with you first part of the proof for quick sort please unless you need more details. Probabilistic fact: For a quick sort please, given that the expected number of coin ...
92 views

### How can I compare two algorithms using their Big-Oh complexities?

I have two recursive algorithms to solve a particular problem. I have calculated their time complexities as $O(n^2\times\log n)$ and $O(n^{2.32})$. I need to find which algorithm is better in terms of ...
31 views

### Space complexity of Bubble sort

I have the following implementation of Bubble sort where it calls a helper method named swap. ...
84 views

### Is the running time of an algorithm that has O(n^2) where n = 10^5 equal to one that has O(1000000n) where n = 10^ 5?

Hello my question is that if i have two for loops inside each other like this: ...
47 views

### If f(n) = O(g(n)), g(n) = O(h(n)), is h(n) = Ω(f(n)) true?

I have $f(n) = O(g(n))$ and $g(n) = O(h(n))$. Is $h(n) = \Omega(f(n))$ true, and if so, what constants would make it true? I was thinking that since $f(n) = O(g(n))$ and $g(n) = O(h(n))$ are true, ...
1k views

### Why is my implementation of Dijkstra's Algorithm using min heap faster than using an unsorted array for a complete graph?

Based on theory, the implementation using adjacency matrix has a time complexity of E+V^2 and the implementation using min heap has a time complexity of (E+V)logV where E is the number of edges and V ...
27 views

### Does clog(n)-c+1 work for T(n)=T(⌈n/2⌉)+1=O(log(n)) after induction?

The given problem is from CLRS, exercise 4.3-2. Show that the solution of T(n)=T(⌈n/2⌉)+1=O(log(n)) I decided to prove T(n) ≤ clog(n) and this is the result I got:...
40 views

### Array Doubling Size Strategies

I would like to discuss resizing strategies for arrays please. If you have an array of $k$ initial size and it gets full, so you would like to choose from one of the following approaches: Approach 1: ...
23 views

### Solving the recurrence using Master or Akra-bazzi theorem

I was trying to use Akra-bazzi theorem for the recurrence equation below for time complexity, but I do not get any value of p that satisfies the condition $\sum a_i b_i^p = 1$ for the equation below. ...
39 views

### Pseudo-polynomial Algorithms

Reading wikipedia I found that they give this example Consider the problem of testing whether a number n is prime, by naively checking whether no number in $\{2,3,\dotsc ,\sqrt {n}\}$ divides $n$ ...
33 views

### Differences between Polynomial and fully polynomial time approximation scheme

I have a confusion on understanding the relation between: The input n ,The relative error and The running time of the program In both PTAS and FPTAS. In "The running time of PTAS must be ...
30 views

### Polynomial and fully polynomial time approximation scheme

How to notice the type of algorithm whether it is polynomial or fully polynomial time approximation from the resulting running time ( execution time) of the program? Is there any other way to decide?
89 views

### Why there is $\log n$ factor in time constructible definition?

I saw two different definitions of time constructible functions. In Sipser (third edt), Definition 9.8, defines $t(n)$ is time constructible if $t(n)\geq O(n \log n)$ and maps $1^n$ to the binary ...
30 views

### Logarithmic space and time computable function for sequences over $\{0,1\}$

Given $\sigma_1 \dots \sigma_n$ a sequence or word of length $n$ over $\{0,1\}$ I was wondering if there is a computable function to calculate $\sigma_m$ in $\log(P(n))$ time where $P(n)$ is some ...
239 views

### Runtime complexity of algorithm that subtracts progressively larger amounts

How would you describe the runtime complexity if I have an algorithm that at each step, the size of the array reduced by an exponentially-increasing amount? For example, for each step in the algorithm,...
31 views

### Self Organizing List vs Hash Table Preformance

I am wondering what the advantages and disadvantages of a self organizing list are over hash tables. Also, does a self organizing list run faster with a memory access pattern, but the memory access ...
49 views

### Running time analysis of Savitch's algorithm

Savitch provided an algorithm which places NL in L^2 and hence the runtime of the algorithm is bound by $2^{O(\log^2n)}$. The runtime of the algorithm is not in P as NL is not known to be in SC. Is ...
52 views

### Why 2^(2n+2) not equal to θ(2^2n)?

I'm trying to prove this expression 2^(2n+2) ≠ θ(2^2n)? Firstly 0 <= c1.2^(2n) <= 2^(2n+2) for this n=1 c1=1 is a solution set. For n = ∞, 0 <= ∞.c1 <= ∞ c1=1 is provide it. So omega ...
84 views

### Runtime of sorting algorithms given a particular input

say that we have {2,3,5,4,6} as input that we want to sort in ascending order. Then, we know that we can use any of the sorting algorithms: bubble, insertion, selection, quick, merge, heap or counting....
90 views

### Understanding the upper bound proof for quick sort

I'm trying to understand the average run time of quicksort which is $O(n \log n)$. I understand the intuition behind it: if we partition array $A$ to e.g. $\alpha n$ and $(1-\alpha)n$ then we ...
80 views

### Why does it take O(n!) time to specify a canonical ordering for learning flatten adjacency matrices/graphs?

I was reading a paper for learning graphs (paper is GraphRNN) and it says in section 2.2 (emphasis by me): Vector-representation based models. One naive approach would be to represent G by flattening ...
113 views

### $(\log n)^{\log n}$ lower-bound and upper-bound

we know that $n \geq \log{n}$ however I understand that $(\log n)^{\log n}$ grows faster than $n$. I have been trying to prove this however I can't seem to figure it out.