Questions tagged [runtime-analysis]
Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.
939
questions
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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:
...
0
votes
0answers
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 ...
0
votes
2answers
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 ...
1
vote
1answer
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 ...
-3
votes
0answers
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?
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
3
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
3answers
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: ...
0
votes
0answers
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 ...
0
votes
4answers
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 ...
0
votes
1answer
31 views
Space complexity of Bubble sort
I have the following implementation of Bubble sort where it calls a helper method named swap.
...
1
vote
3answers
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:
...
1
vote
1answer
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, ...
3
votes
3answers
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 ...
1
vote
0answers
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:...
0
votes
1answer
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: ...
0
votes
0answers
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.
...
0
votes
0answers
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$ ...
0
votes
1answer
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 ...
0
votes
1answer
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?
2
votes
0answers
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 ...
0
votes
0answers
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 ...
2
votes
2answers
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,...
0
votes
0answers
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 ...
3
votes
0answers
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 ...
-1
votes
1answer
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 ...
0
votes
3answers
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....
2
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
3answers
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.
1
vote
2answers
75 views
Silly question: what counts as a "unit of work" when computing big-Oh time complexity
I am going through a fairly non-rigorous textbook called 'Cracking the code interview' and I am bothered by this terminology called "unit of work".
It says in the textbook that certain ...
0
votes
1answer
45 views
Sort an array in specific bounds [duplicate]
Given an array with size of $n$ and except from $\sqrt{n}$ ( lower value ) elements in the array, all of the other elements are integers between the bounds of [$\sqrt{n}$, $n$$\sqrt{n}$]
I will need ...
3
votes
1answer
46 views
What's the runtime complexity of this algorithm for breaking up string into words?
I am given a input string $s$ ("bedbathandbeyond") and a set of words {"bed", "bath", "beyond", "bat", "hand", "and"}. I need to ...
2
votes
1answer
60 views
Proving Quicksort is $O(n^2)$
So I'm trying to figure out why the worst case of Quicksort is $O(n^2)$.
I know this a very well known problem, but the funny thing is where ever I look (even Wikipedia) gives the following ...
0
votes
1answer
70 views
Find the minimum sum of distances between sets of points to a straight line in a plane
Given $n$ dots on a plane, such as: n couples ($x_i$,$y_i$)
I would like to find a line parallel to y-axis ( $x=b$ ), such that the sum of all of the point's distances from that line will be minimal
...
1
vote
1answer
117 views
Sort a $d$-sorted array
An array is $d$-sorted if every key in the array is located at a distance at most $d$ from its location in the sorted array.
I need to write an algorithm that get a $d$-sorted array of length $n$ and ...
0
votes
0answers
41 views
Complexity of backtracking to find power set given random array of numbers
Given an array of elements which can contain duplicates, this is an algorithm that solves the problem.
...
1
vote
0answers
29 views
Is there a branch of CS about studying function calls branching?
I know little about computer science. I wrote a function that has some ifs and may call itself recursively.
Is there a branch of computer science that studies these possible branches?
I'd like to ...
1
vote
1answer
60 views
Time Complexity of Memoized Solution
I was solving Stone Game II on LeetCode. I was able to come up with a recursive (TLE) solution, which I optimized using memoization. The recursive solution computes a function $u(i,m)$, depending on ...
1
vote
1answer
37 views
Theta bound for runtime analysis of nested while loops
I am trying to fully analyze the running time of $\texttt{nestedLoops}$ in terms of $n$ with a Theta bound.
The Java code I have is as follows:
...
1
vote
2answers
326 views
How does size of list in merge-sort, quick-sort, insertion-sort, matter?
We have been taught that:
Insertion-sort will best work if we have a small list.
Quick-sort will best work if we have a long list.
Merge-sort will best work if we have a huge list.
It is not ...
1
vote
1answer
29 views
Can you substitute functions in Big-$\Theta$ notation?
Say we have some function $f(n)=\Theta(\log n)$ and another function $g(n)=\Theta(n+\log n)$. Is it valid to substitute $f(n)$ for $\log n$, giving us $g(n) = \Theta(n + f(n))$? This seems obvious to ...
1
vote
2answers
82 views
Solving $T(n) = 2T(\frac{n}{2}) + n\log(n)$ without master theorem
Solving $T(n) = 2T(\frac{n}{2}) + n\log(n)$ without master theorem, given $T(1) = 1$
My approach with recurrence tree:
$n \sim n\log(n)$
$\frac{n}{2} \sim 2 \frac{n}{2}\log(\frac{n}{2})$
$\frac{n}{4} \...
0
votes
0answers
40 views
substitution method - proving karatsuba algorithm is not O(n)
I want to prove that $T(n) \neq O(n)$ for the Karatsuba algorithm, which has the following recurrence:
$$ T(n) = \begin{cases} k_1, & \text{if $n$ = 1} \\
3T(n/2) + k_2n, & \text{if $n \gt$ 1} ...
1
vote
1answer
167 views
Prove $T(n) = T(\left \lceil{\frac{n}{2}}\right \rceil) + 1 = O(\log(n))$
As the title said, prove $T(n) = T(\left\lceil{\frac{n}{2}}\right\rceil) + 1 = O(\log(n))$
My approach is to find $c, n_0 \in \mathbb{R}_+$ such that:
$$\forall n \geq n_0, T(n) \leq c\log(n) -d \text{...