Questions tagged [runtime-analysis]

Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.

Filter by
Sorted by
Tagged with
0
votes
2answers
69 views

How could a total asymptotic runtime exceed the upper bound of an algorithm's runtime?

This question is specifically related to https://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm The $gcd(x,y)$ is solved in $O(T(n) log n)$, where $n$ is the number of bits ...
0
votes
0answers
27 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
0answers
22 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
18 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 ...
2
votes
1answer
33 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\}$ ...
2
votes
2answers
528 views

Average Case Complexity Rivisted

I got confused with the analysis of algorithms in average case. Following is the my perception regarding average case using sorting problem: Suppose we have a 5 elements array to be sorted using ...
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
42 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 ...
1
vote
1answer
71 views

Analyzing time complexity of solution in tutorial

Could someone explain time complexity of solution of in this tutorial? I'm having hard time figuring out, how asymptotic bounds for first solution is $O(3^k k)$. What I figured so far is, for ...
0
votes
1answer
28 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
634 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 - ...
0
votes
2answers
68 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? ...
1
vote
2answers
55 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
72 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 ...
2
votes
1answer
35 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)....
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
50 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
36 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'...
0
votes
1answer
416 views

Create a binary search tree from a sorted array: Space complexity reasoning

Here is the Python code. The solution is fairly common and is seen in most textbooks like 'Cracking the Coding Interview' and 'Element of Programming Interviews'. ...
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
55 views

Understanding $O(2^n)$ time complexity due to recursive functions

Consider the following binary recursive fibonassi program: ...
2
votes
2answers
184 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 ...
-1
votes
2answers
347 views

How do I analyze Mergesort that uses Insertion Sort for small inputs?

I know that Insertion Sort is faster when size $N$ is a small number, hence by modifying Merge Sort to use Insertion Sort when size $N$ reaches $K$, can help improve the performance. How do I ...
0
votes
1answer
27 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
0answers
15 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 ...
1
vote
1answer
72 views

Recursion Time Complexity (Half n' Half)

This is my solution for Leetcode 395, and I'm wondering how I can come up with its time complexity: Input: string $s = s_1,\ldots,s_n$, integer $k$ Go over all symbols $s_1,\ldots,s_n$, one by one ...
0
votes
1answer
44 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 ...
8
votes
2answers
2k views

Time Complexity analysis for Map-Reduce model

I am trying to redesign my algorithm to run on Hadoop/MapReduce paradigm. I was wondering if there is any holistic approach for measuring time complexity for algorithms on Big Data platforms. As a ...
0
votes
0answers
14 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
20 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 ...
1
vote
1answer
121 views

Runtime analysis of prime-set computation

I want to find the all primes between 2 and $k-1$. We can come up with an $O(k\log k)$ running time algorithm. I want to compute this set in $O(k)$ running time. For this algorithm is : we are ...
0
votes
1answer
73 views

algorithm analysis - complex dependant nested loop

First of all, I know there are many questions like this on the site. But I think this case is a bit different. Consider the following code: ...
3
votes
2answers
4k views

How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3?

How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3? (where n is a power of 3) I was told it takes: $$2(n-2) + 1 = 2n-3$$ However, I can't seem to figure out ...
2
votes
1answer
47 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 ...
2
votes
1answer
54 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 <...
1
vote
1answer
29 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.
3
votes
1answer
43 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
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
2answers
2k views

Time complexity of kruskal using array data structure

I was going through MST(minimum spanning tree) algorithms in a given undirected graph. By using the disjoint data structure It is fairly easy. All I have to do follow these steps: Sort the edges as ...
1
vote
3answers
114 views

Derive a while loop runs in $\Theta( \sqrt{n} )$

I know for a fact that algorithm A runs in $\Theta(\sqrt{n})$, but how does one derive that fact? Algorithm A i = 0 s = 0 while s <= n: s += i i += 1 ...
2
votes
1answer
45 views

number of comparisons in searching algorithms

i was going thorugh different searching algorithms,Linear,binary and ternary search.Now i want to know the number of comparisons in these. For linear search : ...
18
votes
4answers
50k views

Why does Randomized Quicksort have O(n log n) worst-case runtime cost

Randomized Quick Sort is an extension of Quick Sort in which the pivot element is chosen randomly. What can be the worst case time complexity of this algorithm. According to me, it should be $O(n^2)$, ...
3
votes
2answers
775 views

Finding potential function for dynamic array

About dynamic array, doubling it's size with every element that is beying its limit: From what I understand, the number of operations between the $n$th element and the $n+1$th depending on if $n+1$ ...
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
58 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) =...
1
vote
1answer
40 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.

1 2 3 4 5 17