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
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 ...
30 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 ...
15 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?
44 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" ...
218 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 ...
107 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. ...
74 views

### Convex hull partition of a set of points

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}\...
41 views

113 views

### Complexity of brute force primality test in the number of digits

I'm wondering how to express the complexity of a brute force primality testing algorithm in the number of digits the number under test has. The brute force algorithm just checks whether $n$ is prime ...
332 views

### Why is a heap better than a linked list for implementation of a priority queue?

Using a heap, you have O(log(n)) insertion and O(log(n)) removal. Using a linked list, you have O(n) insertion and O(1) removal. Why is it better to have log-n for both than n for one and constant ...
97 views

### How to find efficiently the minimum modification to avoid close consecutive numbers?

I have an array of sorted numbers: arr = [-0.1, 0.0, 0.5, 0.8, 1.2] I want the difference (dist below) between consecutive ...
58 views

### Is this Time analysis strategy right?

I'm working in the time analysis for an algorithm with two optional optimizations variant applied and followed next approach: Create inputs of different lengths for the algorithm Using these inputs ...
15 views

### Runtime explanation of this function [duplicate]

I am trying to understand the runtime complexity of the below code in terms of n. I know that it is $Θ(n^{4/3})$, but I don't get why. I thought the outer loop runs $log(n)$ times, the second one ...