# Questions tagged [runtime-analysis]

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

806 questions
Filter by
Sorted by
Tagged with
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/...
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: ...
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.
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 ...
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 ...
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 ...
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. ...
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 ...
26 views

### Write an algorithm such that if an element in an MxN matrix is 0, its entire row and columns are set to 0 [duplicate]

For this question, I implemented this: ...
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 ...
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}$$ ...
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 ...
9 views

### How can I analyze the runtime of recursive function that calls another recursive function? [duplicate]

for example the runtime of this program: Thanks!
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, ...
148 views

2k views

...
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. ...
267 views

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 ...