Questions tagged [runtime-analysis]
Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.
835
questions
1
vote
1answer
16 views
Worst-case expected running time for Randomized Permutation Algorithm
I have an algorithm which, when given a positive integer N, generates a permutation of the first N integers (from 1 to N) using a method called randInt(x,y). The method randInt(x,y) will generate a ...
1
vote
0answers
26 views
Is using Fibonacci Heaps in Huffman Code, better than a regular Min-heap?
When using Huffman Code, to generate prefix-code trees for a sequence of letters, CLRS choose to use a normal Min-heap data structure.
Using Fibonacci-heaps instead, are we not able to achieve a ...
1
vote
1answer
20 views
Can someone let me know if my understanding of amortized run time in a dynamic array list is correct?
Am I right in my understanding for amortized time for insertion in a dynamic array list? (dynamic means create a copy double its size and copy existing elements to new one WHEN we reach the current ...
2
votes
2answers
30 views
Does the word “efficient” usually refer to polynomial time or polylogarithmic time?
This question is strictly about terminology.
I'm not an expert in CS, but I've almost always seen the word "efficient" applied to an algorithm to mean "of polynomial runtime". E.g. this question and ...
1
vote
1answer
16 views
Can a more powerful encoding of an input make an algorithm that is polynomial in the number of inputs become exponential?
This is probably a very basic question but one that I am having trouble finding a definitive answer for since this kind of thing is skimmed over in most introductory algorithms courses. Take an ...
1
vote
0answers
25 views
How to find the asymptotic bit cost
I know from a general point of view what big O notation is. I have taken an algorithms class before that was all implementations and did well. I am now in an algorithms class that is mostly theory and ...
2
votes
0answers
34 views
How does the maximum number of guesses needed to win Mastermind (board game) change as the size of the board increases?
Donald Knuth demonstrated that the codebreaker in the board game Mastermind can solve the pattern in five moves or fewer using the following algorithm:
Create a set S of remaining possibilities (...
0
votes
0answers
21 views
Iterative-substitution method yields different solution for T(n)=3T(n/8)+n than expected by using master theorem
I's like to guess the running time of recurrence $T(n)=3T(n/8)+n$ using iterative-substitution method. Using master theorem, I can verify the running time is $O(n).$ Using subtitution method however, ...
0
votes
1answer
20 views
Need help analyzing the runtime analysis of this algorithm/algorithms in general
This is the algorithm I was trying to find the runtime of (doSomething) -
...
-1
votes
1answer
71 views
Asymptotic Analysis of Nested Loops with Conditionals
I'm trying to run an analysis of a set of nested loops so that I can determine the value of variable sum after the outer loop is finished. The code is as follows:
<...
1
vote
0answers
25 views
Time Complexity of a Naive Solution to Merge K Sorted Arrays
There is a leetcode question about merging k sorted arrays. I would like to be able to explain the time complexity of the following naive solution:
...
0
votes
2answers
47 views
Algorithm Running Time
I'll do my best to explain my question but what I'm wondering is how to calculate a theoretical running time of an algorithm. In my textbook I have questions written as such:
If a $\Theta(\log_2{n})...
0
votes
1answer
69 views
Explanation of O(n2^n) time complexity for powerset generation
I'm working on a problem to generate all powersets of a given set. The algorithm itself is relatively straightforward:
...
2
votes
1answer
30 views
Recurrence Relations
I am starting to learn recurrence relations in class and I am having issue with this example:
T(N) = 2N - 1 + T(N-1)
I am bit confused as to get the base case.
I'm sorry if this seems elementary, ...
0
votes
0answers
21 views
Runtime of tree sort algorithm confusion
Can anyone explain to me why the average runtime complexity of the program here - https://www.geeksforgeeks.org/tree-sort/ - is nlogn and not n^2logn? Similarly, why is the worst case time complexity ...
0
votes
1answer
36 views
Solving a peculiar recurence relation
Given recurrence:
$T(n) = T(n^{\frac{1}{a}}) + 1$ where $a,b = \omega(1)$ and $T(b) = 1$
The way I solved is like this (using change of variables method, as mentioned in CLRS):
Let $n = 2^k$
$T(...
0
votes
1answer
43 views
Euclidean algorithm - runtime in specific case
I'm going to solving many times this specific equations:
$$2^{x+y} \cdot c - a^{y} \cdot z = 1$$
in which $$a$$ can be equal to: $$-7,-5,-3,-1,1,3,5,7.$$ And $$x+y$$ will be equal to $$128.$$ It has ...
0
votes
1answer
36 views
Runtime Calculation Sort-Algortihm
I'm really struggling with the following exercise and I would really appreciate your help:
I have to calculate the expected runtime of a sort Algorithm with the following variants:
...
5
votes
2answers
642 views
How can merging two sorted arrays of N items require at least 2N - 1 comparisons in every case?
The HW question, on page 362 of Data Structures and Algorithms in C++: Fourth Editionby Mark Allen Weiss, reads as follows:
Prove that merging two sorted arrays of N items requires at least 2 * N - ...
1
vote
2answers
83 views
What is the time complexity of this “reverse words” algorithm?
I had to write an algorithm that, given the input ['h', 'a', 'r', 'd', ' ', 'i', 's', ' ', 'c', 's'] would return ...
1
vote
2answers
160 views
Analysing worst-case time complexity of quick-sort in different cases
I am trying to understand worst case time complexity of quick-sort for various pivots. Here is what I came across:
When array is already sorted in either ascending order or descending order and we ...
0
votes
0answers
20 views
What is an $O(n \log(n))$ binary sorting algorithm with a guaranteed low scaling constant on the run-time?
Let $O_c(f(n))$ denote that $c$ is the scaling constant for the run-time (e.g. $\text{run time} \leq c\cdot f(n) + B$ if $n$ is large enough)
The absolute lower limit on the run-time for a binary ...
2
votes
1answer
37 views
If I walk through list and delete every out-of-order element I come across, on average how many elements will be left?
I have a uniformly randomly permuted list of length $n$. I walk through the list element-by-element, and delete an element if it's out-of-order (compared to the previous in-order elements of the list)....
2
votes
1answer
75 views
Why is the run time with a loop of this structure considered O(log n)
I used the search function and a good amount of google searches, but wasn't able to get a straight answer on how a loop of the form below, is translated to a proper summation where the function ...
1
vote
0answers
38 views
Hypothetical Situation for sorting in $O(n)$ using median finding machine that works in $O(\sqrt{n})$
In a hypothetical world, we have a machine that can find median of $n$
numbers in $O(\sqrt{n})$. (Of course this machine is not real).
Can we use this machine to sort an array in $O(n)$?
I don'...
2
votes
1answer
34 views
What's the decoding time complexity of LT codes?
LT codes are practical fountain codes that are near-optimal erasure correcting codes.
Simply stated, for encoding a $n$-block message, each packet first chooses a degree $d\in\{1,\ldots,n\}$ ...
1
vote
0answers
35 views
Which function grows faster: N Log N or N^(1+Īµ/ā(log N)) [duplicate]
How would you go about solving this problem?
I thought about using a limit infinity approach, but got confused and Wolfram Alpha didn't provide any explanation.
0
votes
1answer
71 views
Understanding $O(2^n)$ time complexity due to recursive functions
Consider the following binary recursive fibonassi program:
...
2
votes
2answers
203 views
Complexity of cyclic sort
I have this algorithm ("cyclic sort") to sort an array which contains unique numbers from 1 to $n$:
...
2
votes
1answer
56 views
How memory controller reads from RAM with O(1) time complexity?
I am trying to understand how a RAM memory controller gets data with instant access while reading through the memory. Let's say initially, ram gets the data at address 0 and then to get the data at ...
0
votes
0answers
16 views
Simulating Boolean Circuit with RAM
Statement:
Every $T(n)$ size bounded Boolean circuit family, could be simulated with $(T(n))^2$ time bounded Random Access Turing Machine (RAM).
Could you please supply me with a reference to an ...
0
votes
0answers
16 views
Ideal time complexity in analysis of distributed protocol
I need some explanation about the definition of ideal time complexity.
My textbook says:
The ideal execution delay or ideal time complexity, T: the execution
delay experienced under the ...
3
votes
1answer
22 views
Smoothed analysis of the Partition problem
I am studying smoothed analysis and trying to apply it to the Partition decision problem: given $n$ real numbers with a sum of $2 S$, decide whether there exists a subset with a sum of exactly $S$.
...
1
vote
1answer
47 views
Why is $T(n)=3T(n/4) + n\log n$ solvable with Master Method but $T(n)=2T(n/2) + n\log n$ is not?
I am having difficulties in understanding why the recurrence
$$T(n)=3T(n/4) + n\log n$$
is solvable with Master Method but
$$T(n)=2T(n/2) + n\log n$$
isn't?
Despite they both look very similar ...
0
votes
2answers
81 views
In Big-O notation, what does it mean for T(n) to be upper bounded by something
I do not have much experience in mathematics but I would really like to grasp Big-O notation on its mathematical level. I already read What does the "big O complexity" of a function mean? ...
2
votes
1answer
59 views
Worst case runtime for binary search
The run time of binary search is O(log(n)).
log(8) = 3
It takes 3 comparisons to decide if an array of 8 elements contains a given element.
It takes 4 comparisons in the example below.
python2.7
<...
3
votes
1answer
47 views
Is it possible to determine if 2 arrays contain the same elements (ignoring duplicates) in faster than O(n log n) time?
So given 2 arrays of equal length, is it possible to determine whether the 2 arrays contain the same elements (ignoring duplicates and where those elements have a total order relation) with time ...
0
votes
1answer
29 views
runtime to a BFS flood-fill with multiple centres?
If we have a flood fill algorithm which, given a number of centres reprenting pixels on an image, runs a BFS flood-fill on them, checking the pixels 4 neighbours, changing their colours and adding ...
0
votes
1answer
45 views
Upper bound for runtime complexity of LOOP programs
Recently I learned about LOOP programs, which always terminate and have the same computational power as primitive recursive functions.
Furthermore primitve recursive functions can (as far as I ...
0
votes
0answers
29 views
sequence of insert and delete operation in (2,3)-tree
I need help by understanding a theorem and its proof from a script. It says "There is a sequence of $n$ insert and delete operations in a (2,3)-tree that require $\Omega ($n log n$)$ many split and ...
0
votes
1answer
17 views
Determining whether a change in an memoized algorithm will improve the performance
I have an algorithm that constructs an optimal binary tree using dynamic programming. After introducing what I thought would be an optimization, the algorithm became over 2 times slover. Question: Is ...
1
vote
1answer
38 views
Is log(n) equivalent to (log(n))^x for big-O analysis?
My professor noted that we could treat any logarithmic function with an exponent as equivalent to log(n) for the purposes of big-O analysis.
ie. $(n log(n) + 1)^2 + (log(n) + 1)(n^2 + 1)$
From the ...
0
votes
1answer
61 views
Time Complexity of the below code? [duplicate]
here is a nested loop where all the variable are integers.This is another question to the thread. I understood the solution part , but stuck in the time-complexity part.
What is the time complexity ...
1
vote
3answers
62 views
How to mathematically prove that a relation T(n)=T($\sqrt{n}$)+c is O(log(log(n))?
following question, I understood the intuition behind how cutting down the size of input by square root on each iteration leads to O(log(log(n))) complexity.
I tried to derive it on paper.
Let T(n) =...
2
votes
1answer
62 views
Time complexity of finding a node with no incoming edges in a DAG: O(n) or O(m+n)
I'm reading Algorithm Design by Jon Kleinberg. In section 3.6, in order to compute the topological ordering of a DAG, one first finds a root node in this DAG, then deletes it from the DAG. The author ...
1
vote
1answer
30 views
Given a set of sets, find the magnitude (number of elements) of the smallest set containing at least one element from each set
I know that the hitting problem is NP hard, but is it possible to find the magnitude of the smallest set? Also, provide the runtime.
0
votes
1answer
29 views
Necessary conditions for proving If f(n) = O(g(n)), then is log(f(n)) = O(log(g(n)))
I am learning about algorithmic complexities and I read that if f(n) and g(n) are asymptotically positive functions and if $f(n) =O(g(n))$ then the relationship $log(f(n)) = O(log(g(n)))$ holds.
I ...
0
votes
0answers
94 views
time complexity of 2 sum problem using binary search
this is a popular searching problem and the question is :
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The ...
1
vote
1answer
42 views
Do problems that have unary encodings automatically become unary languages?
This problem has confused me a lot, can any of you help me out.
Thank you.
0
votes
1answer
43 views
Why does this triple loop code have a running time of 1.5lnN * N^2
Hi all, I'm currently going through the Princeton Algorithms course on coursera, and I'm having trouble understanding the answer to this quiz. I think I understand where the $\frac{1}{2} N^2$ term ...
