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
5
votes
1answer
109 views

What is the runtime of the 'Risch Algorithm'?

I have been trying to find the upper bound on the runtime of the 'Risch algorithm' used for finding the integral of mathematical functions, but have been unable to do so. https://en.wikipedia.org/...
0
votes
0answers
193 views

Run time analysis of a program with nested for loops

Problem Let's say we are given a program and we want to find an algorithm that analyses its asymptotic complexity. This program can only have two types of statements: ...
-1
votes
2answers
2k views

Time complexity of searching an element in Binary Search Tree [closed]

I want to know what will be the time complexity to search, insert and delete an element in a) balanced binary search tree. b) unbalanced binary search tree.
3
votes
2answers
3k views

How do we derive the runtime cost of Karatsuba's algorithm?

I've read the Wikipedia article explaining the complexity analysis of the Karatsuba algorithm, but I'm not fully grasping it. I seem to have gotten about 75% of the way to the solution on my own, but ...
5
votes
1answer
14k views

Best-Case Running Time For Binary Search Tree Insertion

The notion of best-case running time is kind of ambiguous for me. According to wikipedia, the definition of best case running time is: The term best-case performance is used in computer science to ...
-2
votes
1answer
322 views

How to get O(Big-oh) notation for following Code [duplicate]

What i came up with is this 1) inner loop goes to 2n and at each. step it increments n/3 times threfore 2log n times it will execute 2) outer goes to n incrementing by 1 threfore n times Hence for ...
1
vote
2answers
620 views

Determining time complexity of this function in python [duplicate]

I would like to determine the time complexity of this function, in $\mathcal{O}$-Notation. ...
0
votes
0answers
187 views

Running Time of Ford Fulkerson where all edges have equal capacity

My intuition says it would simply be the number of edges leaving s. I'm assuming it's a valid flow network so sum of capacities leaving s is the same as the sum of capacities entering t, so a max flow ...
2
votes
1answer
1k views

What is the time complexity of memory allocation assumed to be?

It is well-known that dynamic arrays have an amortized $O(1)$ time complexity for adding one item, but a worst-case $O(n)$ complexity. This is because for particular values of $n$, there is no more ...
1
vote
0answers
173 views

Median-of-Medians algorithm, calculating the constant c

I'm having trouble understanding how the calculation of the constant $c$ in the Median-of-Medians-algorithm is build up ($cn$). The only calculation I found was on Wikipedia: $$\frac{2g(g-1)}{g-3}$$ ...
0
votes
2answers
96 views

Why selection sort will require $O(N)$ time

As per the example given in this MIT OCW link URL https://ocw.mit.edu/courses/civil-and-environmental-engineering/1-124j-foundations-of-software-engineering-fall-2000/lecture-notes/sorting/ Why ...
10
votes
2answers
242 views

Is there any standard for comparing runtimes experimentally?

My situation I am writing a paper presenting a software module I developed and I want to compare its runtime to other modules for the same task. I am aware of the drawbacks of runtime experiments, ...
1
vote
1answer
148 views

The constant in the merge sort recurrence

Assuming that the worst case running time of merge sort can be described with this recurrence: $\ T(n) = \begin{cases} \theta(1) & \text{if }n = 1\\ 2T(\frac{n}{2}) + \theta(n) & \...
0
votes
0answers
204 views

Understanding time complexity for kth minimum in CLRS

In chapter 10.3. Selection in worst - case linear time ($k$th minimum) from Introduction to Algorithms by Cormen, Leiserson and Rivest, the time complexity expected for step 5 of the algorithm ...
4
votes
1answer
4k views

Heapsort for sorted input

What is the running time of heapsort when the input array is in increasing order? How about decreasing order? (I came across these questions in CLRS.) Here is what I have done so far ... For the ...
1
vote
2answers
171 views

Complexity of the algorithm to find occurences of a given number in a given array

I have an algorithm that I think its complexity is O(n^2). However, our teacher insists that the algorithm takes O(n) time. How can it be? Here is the pseudo-code of the algorithm: ...
0
votes
1answer
134 views

Sub-exponential for Subset Sum on the total bit length of the input

Was crawling the internet, and found this in a paper (1) "[...], a variant of dynamic programming called dynamic dynamic programming has been shown to have a worst-case sub-exponential time ...
1
vote
1answer
153 views

Complexity analysis of recurrence with multiple variables

To give background, there's two ways to multiply two complex numbers: Method A: requires 3 multiplications and 5 additions Method B: requires 4 multiplications and 2 additions And it's given that ...
9
votes
3answers
21k views

Big O: Nested For Loop With Dependence

I was given a homework assignment with Big O. I'm stuck with nested for loops that are dependent on the previous loop. Here is a changed up version of my homework question, since I really do want to ...
1
vote
1answer
413 views

Comb sort average complexity

The wikipedia page about comb sort claims that the average complexity of comb sort is Omega(n^2/2^p) where p is the number of increments. Take as example an uniform distributed array of 1000 elements, ...
1
vote
3answers
2k views

What is the time complexity of this binomial coefficient algorithm?

Here's a naïve algorithm that computes $ \binom{n}k $ (or "n choose k"), with either $k=0$ or $1\le k \le n$: ...
2
votes
1answer
75 views

Complexity of Search Algorithm

I have an algorithm which searches a sorted int array for two elements which sum up to a searched value. First I thought that the complexity is $\mathcal{O}(n)$, but the interpolation search algorithm ...
0
votes
1answer
46 views

How to handle the time complexity for an optimization that depends on numerical values

I'm working on an algorithm and there is an optimization I applied that is unpredictable because it depends on calculations done on top of the input trough several iterations, so as the input values ...
14
votes
4answers
2k views

Are there any algorithms or data structures that need to find the median value of a set?

I have been reading this book for my class, Randomized Algorithms. In this particular book, there is a whole section dedicated to finding the median of an array using random selection, that leads to a ...
0
votes
2answers
65 views

Quick sort analysis confusion

Is randomized quick sort runtime is independent of the sequence of input? but depends on the numbers in the input? Let say A1 = [1,2,3,4,5] , A2 = [5,2,3,4,1] A3 = [5,4,3,2,1] , Will the randomized ...
1
vote
0answers
48 views

Find fastest sort for given range of numbers

I encountered a question from a test that I cant understand the answer given a range of numbers $[0...(logn)^{logn}-1]$ we need to find the quickest sort available and give his running time now ...
2
votes
0answers
180 views

How does one heuristically determine if an algorithm has an exponential time complexity?

How does one easily determine if an algorithm has an exponential time complexity? The Word Break naive solution is known to have a time complexity of O(2n) but most people think its O(n!) because of ...
1
vote
1answer
810 views

How to handle the repeat until convergence condition in time complexity and summarize the time complexity? [closed]

I am a novice in complexity calculation. I need to calculate the overall time complexity. My attempt is given below: Here, N = number of data points (N>300), C ...
1
vote
1answer
2k views

What is correct time complexity of the substring generation algo

The naive algorithm for generating all unique substrings involves traversing all the string from 1..n, thus takes $\mathcal{O}(n^2)$, but it also involves ...
2
votes
4answers
611 views

What is more important in an algorithm, small runtime or small memory usage?

I have two client-server protocols which perform the same function but they have different complexities in time (in terms of number of operations) and space (in terms of number of objects of same type)...
1
vote
1answer
410 views

Merging sorted arrays and finding Big O bounds

Say we have $x$ amount of sorted arrays, each with $n$ elements, and we combine them one at a time. So merging the first two arrays would give us $2n$ in terms of cost, and $3n$ for the next array, ...
1
vote
1answer
146 views

Determining asymptotic running time by profiling [closed]

The purpose of performance profiling is to measure program performance. One part of your PA1 assignment asked to measure performance of your d-smooth algorithm to verify if the running time of the ...
33
votes
3answers
44k views

What exactly is polynomial time? [duplicate]

I'm trying to understand algorithm complexity, and a lot of algorithms are classified as polynomial. I couldn't find an exact definition anywhere. I assume it is the complexity that is not exponential....
0
votes
0answers
46 views

time complexity question

I am reading a free algorithms textbook http://www.cse.iitd.ernet.in/~Naveen/courses/CSL630/all.pdf and on page 13 i am stuck on an example they give. "At this time, the fastest computer in the ...
1
vote
2answers
150 views

What is the time complexity of text justification algo?

The following algo is a simplified version of a text justification algo taken from dynamic programming lecture notes of MIT OCW. I am confused why this particular algo has a time complexity of $\...
-1
votes
2answers
2k views
1
vote
1answer
1k views

Proof of bucket sort worst case being all elements in one bucket

By bucket sort I mean on dividing numbers between 0 and 1 into $n$ buckets and performing insertion sort on all the buckets. ...
2
votes
0answers
267 views

Analysing Dijkstra Algorithm by using different varieties of Data Structure

Question I want to analyse Dijkstra Algorithm by using different varieties of Data Structure. My solution Adjacency matrix to Store the Graph and Binary heap for Priority Queue. $...
2
votes
1answer
947 views

How to understand the analysis of expected running time of randomized quick-sort in this paper?

I'm learning the book named Data Structures & Algorithms in Python. On Page 557-558, there is a proof of the expected running time of randomized qucick-sort. I have some problems confusing me ...
1
vote
4answers
97 views

Locate all locations in a sorted array where arr[i]<arr[i+1]

Suppose you are given an array of $n$ integers with duplicates in non-decreasing order. The goal is to find the locations where a value is different from its neighbor. For example, given the array $...
1
vote
2answers
84 views

quicksort - Why is $\log_4 n$ used as an approximation instead of $\log_2 n$? [closed]

Below is an excerpt from Khan Academy's Quick Sort Analysis page. In the average case of quicksort they assume that each time the partition function breaks the input array into the ratio 1:3 each ...
0
votes
1answer
141 views

Does my Algorithm Qualify as MergeSort?

I've been trying to internalize some of the basic sorting algorithms recently, and to do so I've been looking at their wikipedia pages to refresh myself with how they work, and then coding my own "...
0
votes
0answers
59 views

What is the complexity of my algorithm to solve this kind of system of nonlinear equations?

My algorithm solves the following problem: $n\in\mathbb{N} \land n\ge1$ $\{v_1, \ldots , v_n\}\subset\mathbb{Q}$ $ \begin{eqnarray} \left\{ \begin{array}{} \square\cdot\square\cdot\square = 0 \\ \...
0
votes
0answers
279 views

How to calculate the depth of the call stack for the average case of quicksort

In the best case of quicksort the depth of the call stack is measured by $\lceil\log_2 n\rceil$ if I am not wrong. What would be the formula for calculating the depth of the call stack in case of an ...
3
votes
1answer
7k views

How to prove that average complexity is N/2 for linear search in the unsorted array [duplicate]

All tutorials on algorithms show the complexity for the linear search in the unsorted array in the average case as N/2. I understand that the average case means the ...
4
votes
2answers
1k views

Why does linear search have $\frac{n}{2}$ comparisons on average?

I'm reading the Wikipedia page on Linear Search and it is mentioned that there are on average $\frac{n}{2}$ comparisons. I tried working this out on my own. First I considered the number of cases. ...
0
votes
0answers
87 views

QBF in APTIME - Why APTIME and not ALOGSPACE?

I have a brief proof about QBF being $\in$ APTIME, which claims that you can use the additional input of the alternation as values for your QBF formula. And therefore you can accept, if the ...
2
votes
2answers
882 views

Why are unbalanced partitions worse than balanced partitions in Quicksort?

I am unable to understand why unbalanced partitions in quicksort is actually worse than balanced partitions. After reading this document it shows that worse case partitions are of the type $(0,(n-1)),...