We’re rewarding the question askers & reputations are being recalculated! Read more.

# Questions tagged [runtime-analysis]

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

801 questions
Filter by
Sorted by
Tagged with
686 views

### Analysis of algorithms, 'big O' question

The main question is, how exactly is the big O analysis calculated on routines? Is there a specific formula that relates what each function in a program does to a big O calculation? Also, what about ...
844 views

### What constitutes one unit of time in runtime analysis?

When calculating runtime dependence on the input, what calculations are considered? For instance, I think I learned that array indexing as well as assignment statements don't get counted, why is that?
323 views

### Why don't we emphasize “length of input string” when considering time complexity of sorting algorithms?

The knapsack problem is $O(c\,n)$ where $c$ is the capacity of knapsack and $n$ is the number of items. Yet it's exponential because the size of the input is $\log(c)$. However, why don't we ...
88 views

### Complexity of a particular algorithm

I am a bit confused about calculating complexities. Above is a C++ program converting a char array into an int, incrementing the value, parsing it back to char array. ...
218 views

### Doubt with a problem of grown functions and recursion tree

I'm confused to conclude the recursion tree method a guess for the next recurrence: $$T(n)=3T\left (\left\lfloor \frac{n}{2}\right \rfloor\right) +n$$ I write some costs for the levels of tree, you ...
214 views

### Complexity of an algorithm for bounding a region in 2D

First I apologize if the title is unclear, but I didn't find anything better. I'm solving a differential equation that has two parameters , here denoted by points of a plane.These parameters are real ...
4k views

### Complexity of finding the largest $m$ numbers in an array of size $n$

What follows is my algorithm for doing this in what I believe to be $O(n)$ time, and my proof for that. My professor disagrees that it runs in $O(n)$ and instead thinks that it runs in $\Omega(n^2)$ ...
200 views

### Finding the lower bounds of an algorithm

I am struggling to calculate the lower bounds of an algorithm. What is the right way to proceed. For eg, I have the following algorithm ...
128 views

### Why don't we scale the cost of memory access when analyzing runtime of algorithms?

Runtime for many programming languages is typically analyzed either assuming each operation takes a constant amount of time, or assuming each operation takes a logarithmic amount of time in the size ...
556 views

### Predecessor query where the insertion order is known

Assume I want to insert elements $1$ to $n$ into a data structure exactly once, and perform predecessor queries while inserting these elements (so insert(x) and <...
107 views

### Resolving this recurrence equation [duplicate]

I have this recurrence equation: $T(n) = T(n/4) + T(3n/4) + \mathcal{O}(n)$ $T(1) = 1$ I know that the result is $\mathcal{O}(n \log n)$ but i don't know how to proceed.
1k views

6k views

### Complexity of a while loop that divides by parameter by three each iteration

I've learned that a while loop such as int i = 100; while (i >= 1){ ... ///Stuff i = i/2 } will run in logarithmic time, specifically, ...
419 views

### Common Algorithms without Asymptotically Tight Bounds

I can think of functions such as $n^2 \sin^2 n$ that don't have asymptotically tight bounds, but are there actually common algorithms in computer science that don't have asymptotically tight bounds ...
138 views

### How to get the expected running time of an algorithm

I have an algorithm which, basically given an array of $n$ numbers, checks if there is any repeated numbers in the array, and returns true if there is and false otherwise. It uses a direct access ...
7k views

### Why does a recurrence of $T(n - 1) + T(n - 2)$ yield something in $\Omega(2^{\frac{n}{2}})$?

I am trying to analyze the running time of a bad implementation of generating the $n$th member of the fibonacci sequence (which requires generating the previous 2 values from the bottom up). Why does ...
5k views

### Worst case analysis of bucket sort using insertion sort for the buckets

Suppose I am using the Bucket-Sort algorithm, and on each bucket/list I sort with insertion sort (replace nextSort with insertion sort in the wikipedia pseudocode). In the worst case, this would ...
1k views

### Analyzing programs with multiple for-loops

If they were all linked to make a condition such as ($1 < i < j < k < n$), I know how to solve, but the last loop is disconnected so I have no clue on how to do these... the ones like <...
1k views

262 views

### Input to make worst case on big O not possible?

Sorry if this question is very simplistic; I'm just starting out and I'm trying to wrap my head around all this asymptotic bound stuff. When trying to find the upper bound for the worst case of a ...
2k views

### Runtime analysis of a nested loop

I have some difficulties performing the worst case analysis on this algorithm. The outermost loop is executed $2N$ times. The while loop, in the worst case, will increase by $2$ each time, so it ...
2k views

### Iterative binary search analysis

I'm a little bit confused about the analysis of binary search. In almost every paper, the writer assumes that the array size $n$ is always $2^k$. Well I truly understand that the time complexity ...
120 views

### Is it possible to analyse computation?

Take a Turing machine, with a terminating program, convert it to some representation of the machine which captures, in a lossless manner, its state as it performs the computation. So you have a ...
2k views

386 views

### Recursion for runtime of divide and conquer algorithms

A divide and conquer algorithm's work at a specific level can be simplified into the equation: $\qquad \displaystyle O\left(n^d\right) \cdot \left(\frac{a}{b^d}\right)^k$ where $n$ is the size of ...