Questions tagged [runtime-analysis]
Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.
806
questions
10
votes
3answers
20k views
A d-ary heap problem from CLRS
I got confused while solving the following problem (questions 1–3).
Question
A d-ary heap is like a binary heap, but(with one possible exception) non-leaf nodes have d children instead of 2 ...
3
votes
1answer
130 views
Can quantum computer compute the sum of $n$ natural numbers in $\Theta(\log n)$ time?
Classical computer always requires no matter what $\Theta(n)$ time to compute the sum of $n$ natural numbers, but can quantum computer do that in $\Theta(\log n)$ time?
Given that $a$ is an infinite ...
-1
votes
3answers
76 views
Big Oh notation and selection
I wanted to know something about selection and Time complexity,
for example if I had the f.f.g java code:
...
2
votes
1answer
69 views
Is this a correct approch of finding expected runtime of an algorithm?
Consider two algorithms; we analysis their run time only by counting the number of comparisons
...
1
vote
2answers
569 views
Complexity for merging 3 sorted arrays using this specific algorithtm
During an interview I was asked to calculate the big theta complexity for the following algorithm that receives 3 sorted arrays of variable size and returns a new array which has the elements of the ...
2
votes
4answers
1k views
How does size of a number in an array affect time complexity algorithm analysis?
This question stems from this question and this answer. I also want to preface this question by stating that this question is done from the perspective of a RAM (or PRAM if it's more accurate term) ...
1
vote
0answers
40 views
Time complexity of a nested loop [duplicate]
I need to figure out the complexity of the following loop in theta notation but I can't figure it out. Some help would be much appreciated.
...
0
votes
1answer
208 views
Asymptotic runtime of a nested sum
i have to calculate the asymptotic runtime of a nested sum:
Sum $\sum_{n=1}^{log_{4}(n)} \sum_{n=1}^{\sqrt{n}}1$
My solution is $\Theta(log(n) \cdot \sqrt{n})$, which is wrong, because the solution ...
7
votes
4answers
3k views
What is the time complexity of this function?
This is an example in my lecture notes.
Is this function with time complexity $O(n \log n)$?.
Because the worst case is the funtion goes into else branch, and 2 ...
2
votes
1answer
57 views
What is the complexity to show this theorem?
Given a sum of regular expressions, where each regular expression in the sum is n-1 concatenations of 0, 1 and (0+1).
There is need to show that the sum of all regular expressions is either equal to ...
1
vote
3answers
1k views
Nested Loop Time Complexity vs Successive Loops
An algorithm has a calculation whose worst case time complexity $T(x)=O(x^2)$ that outputs solutions $y$ & $z$ for input $x$ (the algorithm's worst case time complexity is greater than quadratic ...
1
vote
2answers
125 views
Asymptotic vs real-world complexity [duplicate]
Let's say an algorithm has an asymptotic time complexity of $\Theta(N)$. However in practice, $N$ is bound by a small upper limit (e.g. the size of a character set). Can we then say the complexity is $...
-1
votes
1answer
73 views
How is the time complexity of an algorithm with successive-nested loops measured?
Does the time complexity of the following pseudo-algorithm simplify as $O(n^2 log(n)) = O(n^2)$?
SOME ALGORITHM
...
-1
votes
1answer
628 views
What is best case and worst case for this algorithm?
I am supposed to create an algorithm for this statement: “Two input lists of size n have at least one element in common”
This is my algorithm:
...
2
votes
3answers
2k views
Time complexity of this while loop
So, i would like to know the time complexity of the following codes:
...
3
votes
2answers
4k views
Best case analysis for Shell sort
The exercises in a textbook I studied asks about the best case for Shell sort. I have scribbled a derivation for the same along the margins almost two years ago. Basically I don't know if this was my ...
0
votes
1answer
709 views
Lower bound on multiplication
I was told that the fastest possible algorithm for integer multiplication is $O\left(n{\log}(n)\right)$. Why would this so?
Can you please show why the fastest multiplication algorithm would ...
0
votes
0answers
25 views
Big O running time for this algorithm[function call from within a loop]? [duplicate]
So the basic doubt i had started with this piece of code
...
4
votes
1answer
3k views
Amortized time cost of insertion into an Array list
A dynamically resizing array list will resize when the number of elements reaches a power of two. So, after n elements inserted, we've resized at sizes 1, 2, 4, ... , n. This also means we've copied ...
2
votes
2answers
5k views
Time complexity of recursive power code
While I was learning about time complexity of recursive functions, I came across this code to calculate $x^n$:
...
0
votes
1answer
773 views
Create a schedule from overlapping events
Let me first sketch my situation. I have a list of events with time slots, and I need to generate a schedule from these. We can assume that I have already validated and ordered the events from lowest ...
2
votes
1answer
165 views
Pseudo code algorithm for beauty contestant question
Say beauty pageants are judged based on 3 criteria: 1) Appearance 2) Personality 3) Talent. A contestant $C$ will beat another contestant $C'$ if she gets higher scores in ALL THREE of the criteria.
...
0
votes
0answers
33 views
What's a good method to decide wheter distributed or parallel computing?
I've already programed a grammatical evolution on GPU with a very satisfactory result (an improvement on time of about 140% with relative small datasets, expecting better results whith big ones). ...
1
vote
1answer
983 views
Running time complexity of Binary Search Trees and Big-Omega
I know that the main operations (Insert, Search, Delete) have a worst-case running time of $\mathcal{O} (h)$. But I wanted to dig into this deeper.
Basically I am having some difficulties ...
1
vote
1answer
614 views
Proof that quicksort's running time is ∼1.39 n log n
In the fourth edition of Sedgewick's Algorithms, it's claimed that the running time of QuickSort is $\sim 1.39n\log_2 n$. I'm trying to find a "simple" proof and explanation of this.
All I know is ...
7
votes
2answers
12k views
A* graph search time-complexity
Some confusion about time-complexity and A*.
According to
A* Wiki the time-complexity is exponential in the depth of the solution (shortest path):
The time complexity of A* depends on the ...
1
vote
3answers
220 views
What is the time complexity of this аlgorithm? O(n * r)
Given function rand7 returns random integer in interval [0, 6]. Your task is to implement function ...
1
vote
1answer
236 views
Calculate the complexity of an algorithm [duplicate]
I have an algorithm here and it wants me to calculate the complexity:
...
2
votes
1answer
452 views
Running time analysis for algorithm that merges $k$ sorted arrays to one sorted array
Given $k$ sorted arrays, the size of each array is $n$ and we want to sort them to one sorted array. assume that $k=2^p$ i.e $k\in\{ 2^1,2^2,2^3,2^4,\dots\}$
I the first step we will merge (the ...
1
vote
1answer
606 views
Calculate execution time from linear speedup
Given an execution time $t(c_1)$ and linear speedup $s$, how do you calculate the execution time for $c_2$ processor cores?
(Assuming Gustafson's law, or in other words, $t(\infty)=0$)
My ideas:
I ...
2
votes
1answer
688 views
time complexity of word break algorithm
I found this question here but I don't think the answer is correct.
Here is the original word break question:
Given a string s and a dictionary of words dict, add spaces in s to construct a ...
-2
votes
4answers
132 views
what is the complexity of this program? [duplicate]
// assume 'n' is given.
What is the time complexity of this code ?
...
4
votes
2answers
195 views
Why Djikstra's algorithm is said to have $\mathcal{O}(|V|^2)$ complexity?
Djikstra's algorithm assigns some number to non-removed vertex each time it finds a path from removed vertex to it. Number of assignments is $\mathcal{O}(|V|^2)$. However, complexity of assignment is ...
2
votes
1answer
66 views
Does this program have a runtime of O(N) or O(n*m)
This question is similar to, but distinct from this one, in that I am considering a specific case that demonstrates an apparent inconsistency in how I see Big-O notation used. I would like to be sure ...
4
votes
2answers
149 views
Efficient N-Ary GCD Algorithm
Are any algorithms known that can compute the greatest common denominator of multiple (more than two) input values more efficiently than just an iterative application of the fastest GCD algorithm for ...
2
votes
1answer
65 views
Expected Time for LookUpSkipList
A skip list
Let C(k) = the expected length of the path that raises k levels backwards.
Thus C(0) = 0
For any node P in the path, with k levels higher to go, there are two cases:
P is a node of ...
0
votes
1answer
161 views
How to show that this variation of the algorithm (that runs until it finds a solution) still has linear expected running time?
In the last section of chapter 3 (page 57) in Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal, a randomized algorithm is discussed for finding the ...
3
votes
1answer
199 views
Theoretical worst case running time of finding a path through a maze?
Given a randomly generated maze of dimensions n x n, with the entrance point always being the top left corner (0,0) and the exit point always being the bottom right corner (n,n) what is the ...
1
vote
2answers
1k views
prove CLIQUE is NP
I am reading a proof on CLIQUE is NP-Complete. The first step is of course to show that CLIQUE is NP.
c is the clique certificate
V = “On input $\langle\langle G, k\rangle, c\rangle$:
...
2
votes
1answer
117 views
Finding a function f(n) which will bring T(n) runtime to O(log^4(n)) (Interview question)
I am having trouble finding the solution to this interview-like question:
$T(n)$ is given as:
$$T(n) = \begin{cases} 1 & n \leq c, \\ 2T(f(n))+1 & n > c, \end{cases}$$
...
6
votes
2answers
1k views
How do you compute the time complexity of distributed algorithms?
How to compute the run-time of distributed algorithms in message passing systems? I was reading across and found it very weird that any computation done in each node is considered to take $\mathcal{O}(...
0
votes
1answer
698 views
Why is Heapsort in O(n log n) if not all n operations take time log n?
let's consider that we already have constructed heap array.
so from this, when we do heap sort, the number of elements that have to be sorted decreased. I mean heap decrease.(which also means heap ...
0
votes
0answers
296 views
Modification of Lomuto's Quicksort algorithm to reduce swaps
Its well known that Lomuto's partitioning algorithm results in too many unnecessary swaps. Can we modify the algorithm in this way:
Initialize a pointer a that points to the first position in the ...
3
votes
2answers
692 views
How to solve the recurrence: T(n) = n*T(n-1) + n?
In a an exercise I'm required to analyze the runtime of recursive function:
...
-1
votes
2answers
364 views
What will be the time complexity for the following search algorithm in a graph? [duplicate]
I have a graph which looks something like below
I am searching for a given string s going down such that at every node it makes a decision (either to visit the ...
0
votes
0answers
273 views
How to calculate runtime complexity of the nested loops with variable length
Suppose I have a task to write an algorithm that runs through an array of strings and checks if each value in the array contains s character. The algorithm will ...
38
votes
3answers
4k views
How is algorithm complexity modeled for functional languages?
Algorithm complexity is designed to be independent of lower level details but it is based on an imperative model, e.g. array access and modifying a node in a tree take O(1) time. This is not the case ...
0
votes
1answer
565 views
Time complexity of BFS with min heap
Given a matrix of size m x n, I am trying to traverse it using BFS from top left corner to bottom right corner. Instead of using a normal queue for BFS, I am using a min heap. For each cell, I am ...
1
vote
2answers
95 views
Exact amount of loop iterations here?
What is the exact number of loop iterations here and how do you find out?
def func(n):
i = 4
while i < n:
print(i)
i = i + 1
The solution says max(...
-1
votes
1answer
19 views
How do I classify the improvement in performance when Hankel functions are replaced with log functions in MatLab?
I am working on a algorithm for acoustic scattering in two dimensions using MatLab, and one of the advantages of this algorithm is that Hankel functions can be replaced with log functions.
For ...
