# 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
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 ...
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 ...
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: ...
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 ...
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 ...
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) ...
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. ...
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 ...
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 ...
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 ...
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 ...
125 views

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