Questions tagged [runtime-analysis]
Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.
912
questions
0
votes
0answers
28 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
30 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
47 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
82 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
40 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
75 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
2answers
50 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
49 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
30 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
38 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
40 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
63 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
108 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
40 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
28 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
35 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
23 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
159 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
25 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
75 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
33 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
126 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{...
1
vote
2answers
338 views
Prove that the worst-case running time of heapsort is $\Omega(n\lg n)$
I'm trying to prove the running time of heapsort on an array sorted in decreasing/increasing order is $\Theta(n\lg n)$ in order to show that the worst-case running time of heapsort is $\Omega(n\lg n)$
...
0
votes
2answers
106 views
Average case running time of quick sort
How to show that the quick-sort algorithm runs in $O(n^2)$ time on average ?
Because on average, the expected running time is in $O(n\log n)$. The algorithm should not be in exponential time.
0
votes
0answers
20 views
Reference request: Learning runtime analysis (Complete material)
I am very curious about learning runtime analysis more than just what MIT courseware provides (The course with Erik Demaine 6.006) And what CLRS offers, which is a nice explanation about asymptotic ...
1
vote
0answers
42 views
Fibonacci Heap that consolidates after every step
The lecturer of my graduate algorithms course suggested that, even if a Fibonacci Heap would consolidate its tree list after every operation (not just when doing deleteMin()), most operations would ...
0
votes
0answers
18 views
Changes in runtime as the input is incremented
I have a bit of problem in the question below, mainly in the case of incrementing the input size (it doesn't seem solvable to me, like, do we just write $f(n)/f(n+1)$ or...), and also the logarithm ...
1
vote
1answer
46 views
Does Master Theorem apply to $T(n) = 4T(n/2) + n^2 \log n$
Based on CLRS Theorem 4.1, master theorem doesn't apply to $T(n) = 4T(n/2) + n^2 \log n$. However, I saw the 4th condition of master theorem on slides of Bourke.
If $f(n)=\Theta(n^{\log_ba}\log^kn)$, ...
-1
votes
1answer
532 views
1
vote
2answers
49 views
Running time question
If I have two kinds of LinkedList $A$ and $B$.
$A$ is a move to front one which means:
>>> lst1 = 1, 2, 3, 4, 5, 6, 7, 8, 9
>>> lst1.contain(7)
True
>>> lst1.to_list
7, 1, ...
0
votes
1answer
48 views
substitution method on T(n) = T(floor(n/2)) + n recurrence
While studying recurrences and the methods for solving them, I'm get confused on the assumption made on the solution of the following problem.
Why we assumed that this inequality holds for all ...
2
votes
2answers
101 views
Trouble finding average case of a find max algorithm
I'm trying to find the average case number of times that max is assigned by the algorithm findMax included below.
...
1
vote
1answer
87 views
Analyzing the Runtime of Shuffling Algorithm
The following is psuedocode used to shuffle the contents of an array $A$ of length $n$. As a subroutine for shuffle, there is a call to Random$(m)$ which takes $O(m^2)$ time for an input $m$. ...
0
votes
1answer
54 views
How to analyse the worst-case time complexity of this algorithm(a mix of Bubble Sort and Merge Sort)?
Suppose I have a sorting algorithm that sorts a list integers. When the input size(the number of elements) $n$ is odd, it sorts using Bubble Sort and for even $n$ it uses Merge Sort. How do we perform ...
1
vote
1answer
50 views
Runtime Complexity of Memoization
I am struggling to analyze the runtime complexity of the following algorithm formally:
Given a string s and a dictionary of words dict(wordDict), add spaces in s to
construct a sentence where each ...
0
votes
1answer
59 views
How to find mean ,max ,min in constant time?
I was asked to be able to find minimum, maximum and mean of a large array in constant time. I used 3 variables to track these statistics and updated them on every insert operation. I don't feel like ...
0
votes
1answer
32 views
Need help with recurrence relation and postcondition of a function
I just wanted to make sure I'm on the right track regarding this.
Here's the function that I'm dealing with:
...
1
vote
0answers
28 views
Running time of random pivot quicksort on random and sorted arrays
I don't understand why I am getting the following execution times for the quicksort with a random pivot.
Times are in microseconds they are the average of five executions.
Random array: ...
1
vote
1answer
13 views
Does n^(1-1/d) always dominate log^d(n)
Hi I am currently learning about orthogonal range search and found two data structures with two different runtimes and wanted to proof that one always dominates the other.
So I found out about k-d-...
0
votes
0answers
34 views
answers Average case analysis of linear search
Suppose we have an array$[1..n]$ and run linear search to find $x$, on it with following specification:
probability of existence $x$ in first half of array is $p$,and probability of existence $x$ in ...
0
votes
0answers
13 views
How to find optimal sweet spot for time-space trade-off?
If an algorithm can solve a problem in X iterations using Y bytes of space, then another algorithm that solves it in less bytes than Y, will usually end up needing to do it in more iterations (or time)...
0
votes
2answers
70 views
Prove by induction that a recurrence has solution $T(n)=\Theta(n^2 \log_{3}n)$
Prove by induction that $T(n)=\Theta(n^2 \log_{3}n)$ where
$$T(n)= \begin{cases} 1 & \mbox{if } n=1,\\ 9T(\lceil n/3 \rceil)+n^2 & \mbox{otherwise.} \end{cases}$$
The base case for $n=1$ seems ...
2
votes
1answer
61 views
Can one find an algorithm whose running time is larger than Ackermann's function?
Is there an example of an algorithm whose time complexity is strictly larger than Ackermann's function?
1
vote
2answers
99 views
About the pseudo polynomial complexity of the KnapSack 0/1 problem
I have read Why is the dynamic programming algorithm of the knapsack problem not polynomial? and other related questions, so this is not a duplicate but just a related pair of questions to clear some ...
5
votes
2answers
172 views
Upper bounds for a binomial coefficient
I have an algorithm with worst-case time complexity in $\mathcal O (\binom{k}{p-1})$, where $k$ is a parameter and $p$ is the input size of that algorithm. I further have determined that $p-1 \leq k $...
0
votes
1answer
43 views
Exact runtime of median of median algorithm
Consider median of median algorithm. If I make to group of size $7$ instead of $5$ then the recurrence equation will be
$$T(n)=T(n/7)+T(5/7\cdot n+4)+O(n),$$
which can be proven by induction equal to $...
0
votes
0answers
28 views
Computational complexity of described algorithm
Is algorithm which schedules tasks to machine and then for every time point in the makespan of machine does an operation considered pseudo-polynomial or quasi-polynomial? (if machine execute tasks ...
0
votes
0answers
87 views
Why the time complexity for following pseudocode is O(n^2)?
So, I was going through the Rod-Cutting problem in the Dynamic Programming section of the Introduction to Algorithms by CLRS.
Here's the rod-cutting problem statement: Given a rod of length n inches ...
1
vote
1answer
43 views
Determing Big Oh Of Given Data
I'm trying to determine the big O time complexity of the following
data set where the first column is the input size, and the second column is the execution time in seconds. Where possible, I should ...
1
vote
2answers
41 views
Need help with this runtime of algorithm with double loops that results in 0
I know with absolute certainty that this is the wrong runtime, but I just wanted to show you how I got to it.
...
