Questions tagged [runtime-analysis]
Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.
905
questions
1
vote
1answer
26 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
36 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
27 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
28 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
19 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
46 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
24 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
1answer
33 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
2answers
59 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
182 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
99 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
19 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
36 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
32 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
127 views
1
vote
2answers
47 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
45 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
92 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
77 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
36 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
38 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
45 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
27 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
57 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
51 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
71 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
151 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
40 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
27 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
75 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
41 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
40 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.
...
0
votes
1answer
76 views
Knapsack Problem with Constraints on Item Values
Given $n$ items with weights $w_1,...,w_n$ and values $v_1,...,v_n$, and a weight limit $W$, the purpose is still maximizing the total value of items to be carried (while not exceeding the weight ...
0
votes
1answer
65 views
How to calculate the runtime of a following code?
Could someone explain how to calculate the Big O notation for a runtime of a snippet of a code?
...
-3
votes
1answer
48 views
0
votes
0answers
32 views
How to Reconcile Apparent Discrepancy in this Algorithm's Runtime?
I'm currently working through Algorithms by Dr. Jeff Erickson. The following is an algorithm presented in the book:
...
0
votes
1answer
51 views
How to calcualte the Big-O complexity of the following algorithm?
I have been trying to calculate the Big-O of the following algorithm and it is coming out to be O(n^5) for me. I don't know what the correct answer is but most of my colleagues are getting O(n^3).
<...
0
votes
1answer
42 views
Intro to Algorithms: asymptotic function analysis
I'm reading "Introduction to Algorithms" 3rd edition by Cormen, Leiserson, Rivest, Stein Page 46. The authors place formal upper and lower bounds on a function which is quadratic. Can ...
0
votes
0answers
12 views
What does increasing the input size by a factor of 100 do to a linearthimic algorithm with the complexity of 2nlog(n)
So far what I've tried to do is break this into parts and work from there
So for the $2n$, increasing by a factor of 100 means the runtime goes up by 100 times
But I get stuck with the log(n) part. ...
1
vote
1answer
117 views
Why is $\log n+\log \frac{n}{2}+\log \frac{n}{4}+\log \frac{n}{8}+\cdots+\log \frac{n}{n}=\Theta (\log^2 n)$?
$$\log n+\log \frac{n}{2}+\log\frac{n}{4}+\log\frac{n}{8}+\cdots+\log\frac{n}{n}=\Theta (\log^2n).$$
The sum of logarithms is the logarithm of the product $n\cdot\frac{n}{2}\cdot\frac{n}{4}\cdot\frac{...
1
vote
1answer
68 views
Why is $\sum_{i=0}^n\sqrt{i}\log_2^2i \geq \Omega(n\sqrt{n}\log_2n)$?
Where $\Omega(f)$ denotes the set of functions with f as lower bound, why is $\sum_{i=0}^n\sqrt{i}\log_2^2i \geq \Omega(n\sqrt{n}\log_2n)$?
How can the function on the left be compared to a whole set?...
0
votes
0answers
269 views
Count Unique Subsequences to Destination?
I am looking at this post:
Jamie is walking along a number line that starts at point 0 and ends at point n. She can move either one step to the left or one step to the right of her current location , ...
0
votes
0answers
32 views
Essence of the cost benifit obtained by using “markings” in Fibonacci Heaps (by using a mathematical approach)
The following excerpts are from the section Fibonacci Heap from the text Introduction to Algorithms by Cormen et. al
The authors deal with a notion of marking the nodes of Fibonacci Heaps with the ...
0
votes
0answers
66 views
Intuition behind the entire (amortized) concept of Fibonacci Heap operations
The following excerpts are from the section Fibonacci Heap from the text Introduction to Algorithms by Cormen et. al
The potential function for the Fibonacci Heaps $H$ is defined as follows:
$$\Phi(H)...
