Questions tagged [runtime-analysis]

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

Filter by
Sorted by
Tagged with
10
votes
3answers
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 ...
3
votes
1answer
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 ...
-1
votes
3answers
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: ...
2
votes
1answer
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 ...
1
vote
2answers
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 ...
2
votes
4answers
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) ...
1
vote
0answers
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. ...
0
votes
1answer
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 ...
7
votes
4answers
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 ...
2
votes
1answer
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 ...
1
vote
3answers
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 ...
1
vote
2answers
125 views

Asymptotic vs real-world complexity [duplicate]

Let's say an algorithm has an asymptotic time complexity of $\Theta(N)$. However in practice, $N$ is bound by a small upper limit (e.g. the size of a character set). Can we then say the complexity is $...
-1
votes
1answer
73 views

How is the time complexity of an algorithm with successive-nested loops measured?

Does the time complexity of the following pseudo-algorithm simplify as $O(n^2 log(n)) = O(n^2)$? SOME ALGORITHM ...
-1
votes
1answer
628 views

What is best case and worst case for this algorithm?

I am supposed to create an algorithm for this statement: “Two input lists of size n have at least one element in common” This is my algorithm: ...
2
votes
3answers
2k views

Time complexity of this while loop

So, i would like to know the time complexity of the following codes: ...
3
votes
2answers
4k views

Best case analysis for Shell sort

The exercises in a textbook I studied asks about the best case for Shell sort. I have scribbled a derivation for the same along the margins almost two years ago. Basically I don't know if this was my ...
0
votes
1answer
709 views

Lower bound on multiplication

I was told that the fastest possible algorithm for integer multiplication is $O\left(n{\log}(n)\right)$. Why would this so?   Can you please show why the fastest multiplication algorithm would ...
0
votes
0answers
25 views
4
votes
1answer
3k views

Amortized time cost of insertion into an Array list

A dynamically resizing array list will resize when the number of elements reaches a power of two. So, after n elements inserted, we've resized at sizes 1, 2, 4, ... , n. This also means we've copied ...
2
votes
2answers
5k views

Time complexity of recursive power code

While I was learning about time complexity of recursive functions, I came across this code to calculate $x^n$: ...
0
votes
1answer
773 views

Create a schedule from overlapping events

Let me first sketch my situation. I have a list of events with time slots, and I need to generate a schedule from these. We can assume that I have already validated and ordered the events from lowest ...
2
votes
1answer
165 views

Pseudo code algorithm for beauty contestant question

Say beauty pageants are judged based on 3 criteria: 1) Appearance 2) Personality 3) Talent. A contestant $C$ will beat another contestant $C'$ if she gets higher scores in ALL THREE of the criteria. ...
0
votes
0answers
33 views

What's a good method to decide wheter distributed or parallel computing?

I've already programed a grammatical evolution on GPU with a very satisfactory result (an improvement on time of about 140% with relative small datasets, expecting better results whith big ones). ...
1
vote
1answer
983 views

Running time complexity of Binary Search Trees and Big-Omega

I know that the main operations (Insert, Search, Delete) have a worst-case running time of $\mathcal{O} (h)$. But I wanted to dig into this deeper. Basically I am having some difficulties ...
1
vote
1answer
614 views

Proof that quicksort's running time is ∼1.39 n log n

In the fourth edition of Sedgewick's Algorithms, it's claimed that the running time of QuickSort is $\sim 1.39n\log_2 n$. I'm trying to find a "simple" proof and explanation of this. All I know is ...
7
votes
2answers
12k views

A* graph search time-complexity

Some confusion about time-complexity and A*. According to A* Wiki the time-complexity is exponential in the depth of the solution (shortest path): The time complexity of A* depends on the ...
1
vote
3answers
220 views

What is the time complexity of this аlgorithm? O(n * r)

Given function rand7 returns random integer in interval [0, 6]. Your task is to implement function ...
1
vote
1answer
236 views

Calculate the complexity of an algorithm [duplicate]

I have an algorithm here and it wants me to calculate the complexity: ...
2
votes
1answer
452 views

Running time analysis for algorithm that merges $k$ sorted arrays to one sorted array

Given $k$ sorted arrays, the size of each array is $n$ and we want to sort them to one sorted array. assume that $k=2^p$ i.e $k\in\{ 2^1,2^2,2^3,2^4,\dots\}$ I the first step we will merge (the ...
1
vote
1answer
606 views

Calculate execution time from linear speedup

Given an execution time $t(c_1)$ and linear speedup $s$, how do you calculate the execution time for $c_2$ processor cores? (Assuming Gustafson's law, or in other words, $t(\infty)=0$) My ideas: I ...
2
votes
1answer
688 views

time complexity of word break algorithm

I found this question here but I don't think the answer is correct. Here is the original word break question: Given a string s and a dictionary of words dict, add spaces in s to construct a ...
-2
votes
4answers
132 views

what is the complexity of this program? [duplicate]

// assume 'n' is given. What is the time complexity of this code ? ...
4
votes
2answers
195 views

Why Djikstra's algorithm is said to have $\mathcal{O}(|V|^2)$ complexity?

Djikstra's algorithm assigns some number to non-removed vertex each time it finds a path from removed vertex to it. Number of assignments is $\mathcal{O}(|V|^2)$. However, complexity of assignment is ...
2
votes
1answer
66 views

Does this program have a runtime of O(N) or O(n*m)

This question is similar to, but distinct from this one, in that I am considering a specific case that demonstrates an apparent inconsistency in how I see Big-O notation used. I would like to be sure ...
4
votes
2answers
149 views

Efficient N-Ary GCD Algorithm

Are any algorithms known that can compute the greatest common denominator of multiple (more than two) input values more efficiently than just an iterative application of the fastest GCD algorithm for ...
2
votes
1answer
65 views

Expected Time for LookUpSkipList

A skip list Let C(k) = the expected length of the path that raises k levels backwards. Thus C(0) = 0 For any node P in the path, with k levels higher to go, there are two cases: P is a node of ...
0
votes
1answer
161 views

How to show that this variation of the algorithm (that runs until it finds a solution) still has linear expected running time?

In the last section of chapter 3 (page 57) in Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal, a randomized algorithm is discussed for finding the ...
3
votes
1answer
199 views

Theoretical worst case running time of finding a path through a maze?

Given a randomly generated maze of dimensions n x n, with the entrance point always being the top left corner (0,0) and the exit point always being the bottom right corner (n,n) what is the ...
1
vote
2answers
1k views

prove CLIQUE is NP

I am reading a proof on CLIQUE is NP-Complete. The first step is of course to show that CLIQUE is NP. c is the clique certificate V = “On input $\langle\langle G, k\rangle, c\rangle$: ...
2
votes
1answer
117 views

Finding a function f(n) which will bring T(n) runtime to O(log^4(n)) (Interview question)

I am having trouble finding the solution to this interview-like question: $T(n)$ is given as: $$T(n) = \begin{cases} 1 & n \leq c, \\ 2T(f(n))+1 & n > c, \end{cases}$$ ...
6
votes
2answers
1k views

How do you compute the time complexity of distributed algorithms?

How to compute the run-time of distributed algorithms in message passing systems? I was reading across and found it very weird that any computation done in each node is considered to take $\mathcal{O}(...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
3
votes
2answers
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: ...
-1
votes
2answers
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 ...
0
votes
0answers
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 ...
38
votes
3answers
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 ...
0
votes
1answer
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 ...
1
vote
2answers
95 views

Exact amount of loop iterations here?

What is the exact number of loop iterations here and how do you find out? def func(n): i = 4 while i < n: print(i) i = i + 1 The solution says max(...
-1
votes
1answer
19 views

How do I classify the improvement in performance when Hankel functions are replaced with log functions in MatLab?

I am working on a algorithm for acoustic scattering in two dimensions using MatLab, and one of the advantages of this algorithm is that Hankel functions can be replaced with log functions. For ...