# Questions tagged [runtime-analysis]

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

769 questions
Filter by
Sorted by
Tagged with
34 views

### Does a loop incremented by two run at (n+1)/2 times?

I recently started on this topic.. so I have to calculate the time complexity of a method that has another method in it and i do not know if i did it correctly.. Below is a code snippet that I tried ...
51 views

### How to find i-th root of n whose remainder is the smallest?

Given a number n, what is the most assymptotically fast algorithm to express it in terms of base^exponent + rem such that rem is the smallest possible and base is limited from 2 to some relatively ...
372 views

### The time complexity for finding the kth smallest number in a min-heap

Suppose that $k < \sqrt n$, what is the time complexity to find the $k_{th}$ smallest number in a min-heap? I thought that we can remove the root element for k times and each time we apply heapify?...
16 views

### Analysis of straight insertion

I'm currently reading through N. Wirths': Algorithms + Data Structures = Programs. I'm not sure, but I think there might be an error in the analysis of the provided straight insertion sort. Screenshot ...
25 views

### Understanding proof of upper bound on complexity of recursive computation of graph chromatic polynomial

This question is about section 2.3 of Wilf's Algorithms and Complexity'' https://www.math.upenn.edu/~wilf/AlgoComp.pdf in which he analyses the complexity of a recursive computation of the ...
9 views

### How to apply AC-3(Arc-consistency 3) algorithm in N-Queen problem?

I am building N-Queen Solver with java. I confused with AC-3 algorithm. I heard that AC-3 can be applied with backtracking algorithm before processing and during the search.The latter is called MAC-3 ...
26 views

### Choosing algorithms and/or data structures at runtime based on input characteristics

I've been reading about Adaptive Computing, i.e. the idea of computer programs taking feedback from the environment at runtime to improve the output in some way. More precisely, my current focus is in ...
44 views

### BigO time complexity of 3 nested for loops

I'm debating with a friend whether a particular function I wrote is $O(N^3)$ or $O(N \times M \times X)$ I believe it is the latter since all 3 variables differ in size. $N = 100, M = 50, X = 10000$ ...
9 views

### Shortcuts/Patterns for being able to calculate the running time of a loop/algorithm? [duplicate]

This is my first question here. I, like many people, suffer from the lack of the ability to be able to determine the running time of algorithms just by looking at them. I've picked up on a few ...
27 views

### Big oh notation run time [duplicate]

I have this Question , I want the answer and show me how to solve it Please : Analyze the running time of the following algorithm using Big-Oh notation ...
13 views

### Growth rate and runtime [duplicate]

Sorry if this maybe a dumb question, just a little confused But with Big-Oh notation, does it measure the runtime or growth rate of an algo? or both?
29 views

### Karp-Rabin - what is the input for the worst case time complexity?

I'm trying to determine the input for the worst case time complexity of Karb-Rabin regardless of the used hash function. However, I'm seeing both of these answers on the Internet: String "AAAAAAAA" ...
236 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'. ...
180 views

### What is the real reason that Bubble Sort runs at O(n) in best case?

In this link https://techdifferences.com/difference-between-bubble-sort-and-selection-sort.html it says that the best case of bubble sort is order of n due to the fact that there would be only ...
38 views

### Running time for Breadth-First-Search vs Depth-First-Search

Can someone explain why BFS is $O(V + E)$ whereas DFS is $\Theta(V + E)$. I understand the definitions of both notations, but I just don't see why the bound for DFS should be tighter than that of BFS. ...
Given a set $S$ of $n$ points in $\mathbb R^2$, denote by $\mathrm{convb}(S)$ the boundary of the convex hull of $S$. Let \begin{align*} S_1 &= \mathrm{convb}(S)\\ S_{i+1} &= \mathrm{convb}\...