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
0
votes
0answers
17 views

2D segment tree query time complexity

These sources cp-algorithms and geeksforgeeks state that query complexity (for example, submatrix sum) of 2-D segment tree is O(logN * logM), because it first descends the tree in the first ...
0
votes
1answer
17 views

A high-level call-by-reference question

First, let $H$ be a graph represented as an array of adjacency lists say. Next, let FindDegree$(H,y)$ be a standard subroutine that takes $H$ and a vertex $y$ in $H$ as input, and that returns the ...
1
vote
1answer
18 views

Solve recurrence where the base case's time complexity is a function of the original input size

I'm trying to analyse the time complexity of the following algorithm for generating the power set: ...
0
votes
0answers
23 views

Intuition behind : recursive algorithm takes exponential time [duplicate]

So I am studying an introductory chapter to dynamic programming that suggests a general solution to an optimization problem that occurs straightforwardly from expressing the problem with a reccurence ...
0
votes
2answers
35 views

Regularity condition for cases 1 & 2

My question concerns the version of the Master Theorem described in CLRS and in this handout. I already understand the following: If the regularity condition in case 3 does not hold, then we can't ...
1
vote
1answer
32 views

Why is the time complexity of merge sort with a $\Theta(n^2)$ merge function $\Theta(n^2)$?

The original problem I was solving was what would the time complexity of a merge sort algorithm be, if it used a merge algorithm with complexity $\Theta(n^2)$ instead of $\Theta(n)$. The solution says ...
-3
votes
0answers
14 views

Bubble Sort Runtime complexity analysis l [duplicate]

I'm trying to find the time complexity of this cod line by line can you help me?
1
vote
1answer
18 views

Karatsube-Ofman runtime complexity computation

I have a question and didn't understand the solution, since we didn't take how to do it in the lecture and it's not explained in the solution sample. Question: One can generalize the Karatsube-Ofman ...
0
votes
1answer
21 views

Insertion Sort running time calculating using summtion

I was reading Introduction to algorithms, and stopped at the calculating the running time. For each $j = 2,3,..,n$ where $n = A.length$, we let $t_j$ denote the number of times the while loop test in ...
0
votes
1answer
31 views

Time complexity when loop index is an exponent

For any $n$ and any $x$, if one implements a loop to calculate: $$\sum_{i=0}^n x^i$$ What is time complexity of said loop if we assume $x^i$ to have time complexity of $O(i)$? What confuses me is the ...
3
votes
1answer
49 views

N points with maximum sum distance

Given a distance matrix for 50,000 points, how do I select $N$ points so that the sum of all distances between the $N$ points is maximized? $N$ could be as high as 100. To calculate the sum of ...
0
votes
0answers
47 views

Optimal Word Guessing Algorithm in $O(n \log n)$

Say that your friend picks a word $(w_1, w_2,\dots,w_n)$ according to a known probability distribution $(p_1,p_2,\dots,p_n)$. You ask yes or no questions until you are certain which word has been ...
1
vote
3answers
148 views

What could be the most efficient algorithm to compare two unsorted arrays?

I have two arrays A and B of the same length n. I am looking to swap such that all the elements of array A are less than each element of B. Elements in A and B can be unsorted. Example Inputs: ...
0
votes
0answers
33 views

Randomized Quick Sort Discussion

I would just like to discuss with you first part of the proof for quick sort please unless you need more details. Probabilistic fact: For a quick sort please, given that the expected number of coin ...
0
votes
4answers
92 views

How can I compare two algorithms using their Big-Oh complexities?

I have two recursive algorithms to solve a particular problem. I have calculated their time complexities as $O(n^2\times\log n)$ and $O(n^{2.32})$. I need to find which algorithm is better in terms of ...
0
votes
1answer
31 views

Space complexity of Bubble sort

I have the following implementation of Bubble sort where it calls a helper method named swap. ...
1
vote
3answers
84 views

Is the running time of an algorithm that has O(n^2) where n = 10^5 equal to one that has O(1000000n) where n = 10^ 5?

Hello my question is that if i have two for loops inside each other like this: ...
1
vote
1answer
47 views

If f(n) = O(g(n)), g(n) = O(h(n)), is h(n) = Ω(f(n)) true?

I have $f(n) = O(g(n))$ and $g(n) = O(h(n))$. Is $h(n) = \Omega(f(n))$ true, and if so, what constants would make it true? I was thinking that since $f(n) = O(g(n))$ and $g(n) = O(h(n))$ are true, ...
3
votes
3answers
1k views

Why is my implementation of Dijkstra's Algorithm using min heap faster than using an unsorted array for a complete graph?

Based on theory, the implementation using adjacency matrix has a time complexity of E+V^2 and the implementation using min heap has a time complexity of (E+V)logV where E is the number of edges and V ...
1
vote
0answers
27 views

Does clog(n)-c+1 work for T(n)=T(⌈n/2⌉)+1=O(log(n)) after induction?

The given problem is from CLRS, exercise 4.3-2. Show that the solution of T(n)=T(⌈n/2⌉)+1=O(log(n)) I decided to prove T(n) ≤ clog(n) and this is the result I got:...
0
votes
1answer
40 views

Array Doubling Size Strategies

I would like to discuss resizing strategies for arrays please. If you have an array of $k$ initial size and it gets full, so you would like to choose from one of the following approaches: Approach 1: ...
0
votes
0answers
23 views

Solving the recurrence using Master or Akra-bazzi theorem

I was trying to use Akra-bazzi theorem for the recurrence equation below for time complexity, but I do not get any value of p that satisfies the condition $\sum a_i b_i^p = 1$ for the equation below. ...
0
votes
0answers
39 views

Pseudo-polynomial Algorithms

Reading wikipedia I found that they give this example Consider the problem of testing whether a number n is prime, by naively checking whether no number in $\{2,3,\dotsc ,\sqrt {n}\}$ divides $n$ ...
0
votes
1answer
33 views

Differences between Polynomial and fully polynomial time approximation scheme

I have a confusion on understanding the relation between: The input n ,The relative error and The running time of the program In both PTAS and FPTAS. In "The running time of PTAS must be ...
0
votes
1answer
30 views

Polynomial and fully polynomial time approximation scheme

How to notice the type of algorithm whether it is polynomial or fully polynomial time approximation from the resulting running time ( execution time) of the program? Is there any other way to decide?
2
votes
0answers
89 views

Why there is $\log n$ factor in time constructible definition?

I saw two different definitions of time constructible functions. In Sipser (third edt), Definition 9.8, defines $t(n)$ is time constructible if $t(n)\geq O(n \log n)$ and maps $1^n$ to the binary ...
0
votes
0answers
30 views

Logarithmic space and time computable function for sequences over $\{0,1\}$

Given $\sigma_1 \dots \sigma_n$ a sequence or word of length $n$ over $\{0,1\}$ I was wondering if there is a computable function to calculate $\sigma_m$ in $\log(P(n))$ time where $P(n)$ is some ...
2
votes
2answers
239 views

Runtime complexity of algorithm that subtracts progressively larger amounts

How would you describe the runtime complexity if I have an algorithm that at each step, the size of the array reduced by an exponentially-increasing amount? For example, for each step in the algorithm,...
0
votes
0answers
31 views

Self Organizing List vs Hash Table Preformance

I am wondering what the advantages and disadvantages of a self organizing list are over hash tables. Also, does a self organizing list run faster with a memory access pattern, but the memory access ...
3
votes
0answers
49 views

Running time analysis of Savitch's algorithm

Savitch provided an algorithm which places NL in L^2 and hence the runtime of the algorithm is bound by $2^{O(\log^2n)}$. The runtime of the algorithm is not in P as NL is not known to be in SC. Is ...
-1
votes
1answer
52 views

Why 2^(2n+2) not equal to θ(2^2n)?

I'm trying to prove this expression 2^(2n+2) ≠ θ(2^2n)? Firstly 0 <= c1.2^(2n) <= 2^(2n+2) for this n=1 c1=1 is a solution set. For n = ∞, 0 <= ∞.c1 <= ∞ c1=1 is provide it. So omega ...
0
votes
3answers
84 views

Runtime of sorting algorithms given a particular input

say that we have {2,3,5,4,6} as input that we want to sort in ascending order. Then, we know that we can use any of the sorting algorithms: bubble, insertion, selection, quick, merge, heap or counting....
2
votes
1answer
90 views

Understanding the upper bound proof for quick sort

I'm trying to understand the average run time of quicksort which is $O(n \log n)$. I understand the intuition behind it: if we partition array $A$ to e.g. $\alpha n $ and $(1-\alpha)n$ then we ...
1
vote
1answer
80 views

Why does it take O(n!) time to specify a canonical ordering for learning flatten adjacency matrices/graphs?

I was reading a paper for learning graphs (paper is GraphRNN) and it says in section 2.2 (emphasis by me): Vector-representation based models. One naive approach would be to represent G by flattening ...
0
votes
3answers
113 views

$(\log n)^{\log n}$ lower-bound and upper-bound

we know that $n \geq \log{n}$ however I understand that $(\log n)^{\log n}$ grows faster than $n$. I have been trying to prove this however I can't seem to figure it out.
1
vote
2answers
75 views

Silly question: what counts as a "unit of work" when computing big-Oh time complexity

I am going through a fairly non-rigorous textbook called 'Cracking the code interview' and I am bothered by this terminology called "unit of work". It says in the textbook that certain ...
0
votes
1answer
45 views

Sort an array in specific bounds [duplicate]

Given an array with size of $n$ and except from $\sqrt{n}$ ( lower value ) elements in the array, all of the other elements are integers between the bounds of [$\sqrt{n}$, $n$$\sqrt{n}$] I will need ...
3
votes
1answer
46 views

What's the runtime complexity of this algorithm for breaking up string into words?

I am given a input string $s$ ("bedbathandbeyond") and a set of words {"bed", "bath", "beyond", "bat", "hand", "and"}. I need to ...
2
votes
1answer
60 views

Proving Quicksort is $O(n^2)$

So I'm trying to figure out why the worst case of Quicksort is $O(n^2)$. I know this a very well known problem, but the funny thing is where ever I look (even Wikipedia) gives the following ...
0
votes
1answer
70 views

Find the minimum sum of distances between sets of points to a straight line in a plane

Given $n$ dots on a plane, such as: n couples ($x_i$,$y_i$) I would like to find a line parallel to y-axis ( $x=b$ ), such that the sum of all of the point's distances from that line will be minimal ...
1
vote
1answer
117 views

Sort a $d$-sorted array

An array is $d$-sorted if every key in the array is located at a distance at most $d$ from its location in the sorted array. I need to write an algorithm that get a $d$-sorted array of length $n$ and ...
0
votes
0answers
41 views

Complexity of backtracking to find power set given random array of numbers

Given an array of elements which can contain duplicates, this is an algorithm that solves the problem. ...
1
vote
0answers
29 views

Is there a branch of CS about studying function calls branching?

I know little about computer science. I wrote a function that has some ifs and may call itself recursively. Is there a branch of computer science that studies these possible branches? I'd like to ...
1
vote
1answer
60 views

Time Complexity of Memoized Solution

I was solving Stone Game II on LeetCode. I was able to come up with a recursive (TLE) solution, which I optimized using memoization. The recursive solution computes a function $u(i,m)$, depending on ...
1
vote
1answer
37 views

Theta bound for runtime analysis of nested while loops

I am trying to fully analyze the running time of $\texttt{nestedLoops}$ in terms of $n$ with a Theta bound. The Java code I have is as follows: ...
1
vote
2answers
326 views

How does size of list in merge-sort, quick-sort, insertion-sort, matter?

We have been taught that: Insertion-sort will best work if we have a small list. Quick-sort will best work if we have a long list. Merge-sort will best work if we have a huge list. It is not ...
1
vote
1answer
29 views

Can you substitute functions in Big-$\Theta$ notation?

Say we have some function $f(n)=\Theta(\log n)$ and another function $g(n)=\Theta(n+\log n)$. Is it valid to substitute $f(n)$ for $\log n$, giving us $g(n) = \Theta(n + f(n))$? This seems obvious to ...
1
vote
2answers
82 views

Solving $T(n) = 2T(\frac{n}{2}) + n\log(n)$ without master theorem

Solving $T(n) = 2T(\frac{n}{2}) + n\log(n)$ without master theorem, given $T(1) = 1$ My approach with recurrence tree: $n \sim n\log(n)$ $\frac{n}{2} \sim 2 \frac{n}{2}\log(\frac{n}{2})$ $\frac{n}{4} \...
0
votes
0answers
40 views

substitution method - proving karatsuba algorithm is not O(n)

I want to prove that $T(n) \neq O(n)$ for the Karatsuba algorithm, which has the following recurrence: $$ T(n) = \begin{cases} k_1, & \text{if $n$ = 1} \\ 3T(n/2) + k_2n, & \text{if $n \gt$ 1} ...
1
vote
1answer
167 views

Prove $T(n) = T(\left \lceil{\frac{n}{2}}\right \rceil) + 1 = O(\log(n))$

As the title said, prove $T(n) = T(\left\lceil{\frac{n}{2}}\right\rceil) + 1 = O(\log(n))$ My approach is to find $c, n_0 \in \mathbb{R}_+$ such that: $$\forall n \geq n_0, T(n) \leq c\log(n) -d \text{...

1
2 3 4 5
19