Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

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
1answer
12 views

Necessary conditions for proving If f(n) = O(g(n)), then is log(f(n)) = O(log(g(n)))

I am learning about algorithmic complexities and I read that if f(n) and g(n) are asymptotically positive functions and if $f(n) =O(g(n))$ then the relationship $log(f(n)) = O(log(g(n)))$ holds. I ...
0
votes
0answers
20 views

time complexity of 2 sum problem using binary search

this is a popular searching problem and the question is : Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The ...
0
votes
0answers
17 views
0
votes
0answers
24 views

proving long asymptotic bounds

I'm trying to find ways this simplify this formula and assuming numbers but that doesn't seem to help, the question is asking to prove or disprove: $$ 3n(\log_{}n)^2 + 4n = \Omega (2n^2 \log_{}n +1) $...
0
votes
1answer
37 views

Why does this triple loop code have a running time of 1.5lnN * N^2

Hi all, I'm currently going through the Princeton Algorithms course on coursera, and I'm having trouble understanding the answer to this quiz. I think I understand where the $\frac{1}{2} N^2$ term ...
2
votes
1answer
23 views

number of comparisons in searching algorithms

i was going thorugh different searching algorithms,Linear,binary and ternary search.Now i want to know the number of comparisons in these. For linear search : ...
0
votes
1answer
37 views

Derive a while loop (which seemingly have some logarithmic traits) runs in $\Theta(n)$

I know for a fact that algorithm A runs in $\Theta(n)$, but how does one derive that? Algorithm A ...
1
vote
3answers
60 views

Derive a while loop runs in $\Theta( \sqrt{n} )$

I know for a fact that algorithm A runs in $\Theta(\sqrt{n})$, but how does one derive that fact? Algorithm A i = 0 s = 0 while s <= n: s += i i += 1 ...
1
vote
1answer
61 views

Running time of algorithm (effect of j*j in for loops) - Theta Runtime

In Theta notation what are the running times of these algorithms? Algorithm 1 for i=1..n j=1 while j*j <= i: j = j + 1 Since the outer loop ...
1
vote
1answer
49 views

Why in BFPRT (median of medians) algorithm the partition of the array by $7$ blocks would work but with the $3$ fail?

I am working with the median-median algorithm or BFPRT algorithm and I seek to understand why would the partition of the array by $7$ blocks would work but with the $3$ fail? If we divide into ...
0
votes
3answers
112 views

How to prove that ($56n^2+106n+48)(\log(264n^2+200)) = Θ(𝑛^2\log n)$

I understand that essentially we have to prove that $$c_1(n^2\log n)\le (56n^2+106n+48)(\log(264n^2+200)) \le c_2(n^2\log n)\,.$$ I am confused on how to simplify this further? And ...
1
vote
1answer
26 views

Runtime-Analysis for single loop incremented by a factor of 3

So, I'm trying to understand how to get the run time of this loop: for(int i = 1; i < n*n*n; i*=3) {...} So, far I know: loop starts at 1 finishes when $i &...
0
votes
1answer
310 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'. ...
1
vote
1answer
19 views

Maximum-cardinality matching in unbalanced bipartite graphs

Let $G = (X+Y, E)$ be a bipartite graph, and suppose we want to find a maximum-cardinality matching in $G$. The Hopcroft-Karp algorithm runs in time $O(|E|\sqrt{|V|})$, where here $|V| = |X|+|Y|$. So ...
0
votes
1answer
43 views

What time complexity is more significant? [closed]

A certain algorithm executes $n$ operations of three types: insert, delete, and find. We know that $n/10$ of the operations are inserts, and the rest are deletes and finds. You are given two ...
0
votes
0answers
23 views

Time complexity of simple function related to bits

I am wondering about correct answer to this task from a yesterday's test: A function Pow which calculates $y = a^k$ is given, where $k$ is an integer of length ...
0
votes
2answers
51 views

Big O analysis for problem where number of items searched is unknown

Consider this problem: you are searching an array of elements and are comparing the square of the current element to some number K. Essentially, you are looking to see if the square root of K is in ...
0
votes
2answers
81 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 ...
1
vote
2answers
433 views

The time complexity for finding the kth smallest number in a min-heap [duplicate]

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?...
0
votes
1answer
23 views

Complexity Class of an Algorithm with two Inputs

Consider a problem with two inputs like (P,L) and |P|=n and L is some positive integer. If my algorithm had a complexity of O(n^L), would that still be polynomial? Or is it exponential? I'm not sure ...
1
vote
3answers
942 views

Meaning of the constants that appear in the Master Theorem

The general formula for time complexity is $T(n) = aT(n/c) + bn^k$. If $a> c^k$, the complexity is $O(n^{\log_c a})$. If $a = c^k$, it is $O(n^k \log n)$. If $a < c^k$, it is $O(n^k)$. $a$ is ...
3
votes
1answer
587 views

Finding potential function for dynamic array

About dynamic array, doubling it's size with every element that is beying its limit: From what I understand, the number of operations between the $n$th element and the $n+1$th depending on if $n+1$ ...
1
vote
1answer
42 views

Recursion Time Complexity (Half n' Half)

This is my solution for Leetcode 395, and I'm wondering how I can come up with its time complexity: Input: string $s = s_1,\ldots,s_n$, integer $k$ Go over all symbols $s_1,\ldots,s_n$, one by one ...
7
votes
2answers
2k views

Time Complexity analysis for Map-Reduce model

I am trying to redesign my algorithm to run on Hadoop/MapReduce paradigm. I was wondering if there is any holistic approach for measuring time complexity for algorithms on Big Data platforms. As a ...
0
votes
0answers
41 views

Proof of the average case of the Heap Sort algorithm

Consider the following python implementation of the Heap Sort algorithm: ...
1
vote
1answer
114 views

Runtime analysis of prime-set computation

I want to find the all primes between 2 and $k-1$. We can come up with an $O(k\log k)$ running time algorithm. I want to compute this set in $O(k)$ running time. For this algorithm is : we are ...
0
votes
1answer
54 views

algorithm analysis - complex dependant nested loop

First of all, I know there are many questions like this on the site. But I think this case is a bit different. Consider the following code: ...
0
votes
0answers
26 views

How many inputs N can be placed into a function ln to get a certain amount of time?

it's "gardening" time, which means studying algorithms. A question in Intro to Algorithms 3rd Edition is a chart asking me how many of N inputs can be placed into a function to get a certain amount of ...
2
votes
1answer
58 views

runtime of 2 dependent nested for loops [duplicate]

for (i=1; i<=n ;i=i*2){ for (j=1; j<=i ;j++){ basic_step; } } Regarding the above nested loops, I can't seem to understand why is the following ...
0
votes
3answers
64 views

Is there a unit of measurement that can express code execution speed in absolute terms?

I've always seen code execution speed measured either in units of time (e.g. t milliseconds), or using asymptotic analysis (e.g. O(n log n)). Execution speed will vary depending on hardware ...
1
vote
1answer
61 views

How to find an algorithm's complexity from actual running times

I have a certain algorithm which I can run, but I do not have access to its code. Thus, it works as a black box. I would like to now the order of complexity of this algorithm on a certain set of ...
0
votes
2answers
38 views

Karatsuba Multiplication Rule in dividing a Number in two parts

In Karatsuba algorithm for multiplying two numbers, we divide each number into two. For example: x= 1234 y= 2456 Then a = 12, b = 34, c = 24 , d = 56 What if ...
2
votes
1answer
35 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 ...
1
vote
1answer
36 views

Average Case Running Time of Quicksort Algorithm

From this website, it states that the average case of Quicksort algorithm is T(n) = T(n/9) + T(9n/10) + θ(n) Im a bit confused. Is it supposed to be ? ...
2
votes
1answer
19 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 ...
0
votes
0answers
19 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 ...
0
votes
0answers
30 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 ...
-3
votes
2answers
85 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$ ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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?
0
votes
2answers
41 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" ...
1
vote
2answers
210 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 ...
2
votes
1answer
74 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. ...
1
vote
0answers
73 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}\...
1
vote
2answers
41 views

Running time correct with Omega?

I have the following statement. I would say it's correct as it's either equal or higher than $\Omega(\log^{10}(n))$. Because: I know $\log(2^n) = n$. By that I would guess the same goes for $\log(n^{...
1
vote
3answers
86 views

What should I call algorithms with non-linear non-constant time?

I am writing a paper in which I want to refer to a group of algorithms. Some of these algorithms are of complexity O(NlogN), and some of the are more complex (e.g ...
1
vote
2answers
229 views

3 * O(n^2) vs O(n^3)

Currently while I was coding, I got a doubt. While I was solving a particular type of problem I found it to be solved in $O(n^3)$. I have broken that problem and solved it in $O(n^2)$. But to ...
0
votes
0answers
19 views

Run time of pseudo code in big theta notation [duplicate]

I am looking for the run time of the following pseudo code. ...
0
votes
1answer
78 views

Worst Case Scenario for Quicksort algorithm with pivot element n/2

What would the worst case array look like if I decide to always take the element on the position $\frac{n}{2}$ as the pivot element? I know that if I choose the left or rightmost element as pivot ,the ...