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.

Filter by
Sorted by
Tagged with
0
votes
2answers
23 views

Runtime analysis of bit operations

In class we have learned that division takes O($k^2$) where k is the bitlength of the numbers used in the operation. What would be the runtime of a function that looks like this? ...
-1
votes
2answers
98 views

Big-O notation analysis [duplicate]

Can I get help to give an analysis of the running time Big-O? I'm not sure if all my answers are correct. I got for a) $ O(n)$, b) $O(n^3)$, c) $O(n^{1/2})$ and d) $O(log(n))$ ...
0
votes
0answers
198 views

Time complexity of inorder run on B+ tree (without leavesa link)

I quite sure that it should be $O(n)$, but I didn't found any information about it and I'm not sure how to prove it. Maybe in 2-3 tree the max number of node (include the leaves) is $2n$ and in each ...
1
vote
1answer
154 views

Cost of break statement

i am trying find the Cost of an algorithm. it contains break statements. is there any cost of break and Continue statement in a Algorithm?
1
vote
2answers
645 views

Time complexity of euler totient function

Code for finding $\phi$(n) is ...
1
vote
2answers
236 views

Confusion over the complexity of parameter passing in merge sort

I'm working through CLRS on problem 4-2, which says the following: Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an $N$-element array is ...
1
vote
2answers
597 views

Solving complexity using summation

I have the following algorithm: func() { for(i=1; i<n; i=i*2) print("aa"); } How can I find Big-Oh using summation?
0
votes
1answer
306 views

Amortized time of insertion into an Array list

According to 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'...
1
vote
2answers
1k views

EXTRACT MIN algorithm for Young tableau

This are two sections from a task I got. The Young tableau is defined as a matrix of m rows on n columns so that the bars in each row are sorted in ascending order Left to right and the ...
0
votes
1answer
39 views

Can I assume that a percentage of the time can be parallelized?

I study computer science and hardware. Some problem are about parallel computing and applied Amdahl's law. For instance, some calculation is that the sequential part of a program takes x seconds and ...
1
vote
1answer
542 views

Complexity of while loop using series

For the following code fragment: i = 1; s = 1; while(s <= n) { i++; s = s+i; printf("x"); } How can we go about proving the time complexity of ...
0
votes
1answer
84 views

Complexity of a loop

If the body of a simple for loop has time complexity $O(n)$ and it is executed $n-1$ times what is the time complexity of the complete loop? I am trying to figure out the correct answer to this ...
1
vote
2answers
2k views

Big O notation for recursive algorithm [duplicate]

In order to find Big O for a recursive algorithm, it is needed to know the stopping criteria of that algorithm. For the recursive algorithm to find Factorial of a number it is very easy to find the ...
3
votes
0answers
950 views

Analysis of Weighted Quick Union with Path Compression

I have searched the internet for an analysis of why WQUPC is amortized $O( m \alpha (n) ) $ for m operations on n nodes ( $\alpha ( n) $ is the inverse Ackerman function). I understand why it is $O ( ...
0
votes
2answers
183 views

Why and how geometric series are used for proofs?

I often see that someone uses geometric series for proofs related to time complexity, but also I can't understand why they are used. Are they making proving easier? And how can I use this 'tool' for ...
0
votes
0answers
81 views

How many operations does this algorithm require?

I have the following algorithm x = 0 S = {} k = 1 while x + a[k] < n do S = S + {k} x = x + a[k] k = k + 1 end where ...
0
votes
0answers
199 views
1
vote
1answer
52 views

Runtime analysis of bit sorting algorithm with input size and integer size

I'm struggling to analyze the runtime of this algorithm mainly because it depends on two parameters - the length of the input n, and also the bit size of individual n (bitnum). Most documentation I ...
1
vote
1answer
358 views

A plane-sweep algorithm for a points in triangles inclusion problem

I was given the following homework assignment: Consider a set of $p$ points and $t$ triangles in the plane. The triangles are pairwise disjoint, that is, their edges do not intersect, no triangle ...
2
votes
1answer
2k views

Recursion call inside a for loop time

I'm analyzing a piece of code that has a recursive call inside a for loop such as: ...
0
votes
0answers
73 views

Time Complexity — Recursion

It's been a long time since I've studied time complexity in school, but I've been tasked with finding the time complexity of an algorithm. Here is the algorithm in a pseudo-pseudocode (yes, two ...
0
votes
1answer
55 views

How could a total asymptotic runtime exceed the upper bound of an algorithm's runtime?

This question is specifically related to https://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm The $gcd(x,y)$ is solved in $O(T(n) log n)$, where $n$ is the number of bits ...
2
votes
0answers
68 views

A question on analysis of the time complexity of a recursive branching algorithm

I'm reading papers on algorithms of maximum independent problem and the basic recursive branching rules is as follows: Let $G(V,E)$ be an $n$-node undirected, simple graph without loops, and $\...
0
votes
0answers
223 views

Analysis of finding the k-th largest element in a subsegment of an array

Given an array $A$ of length $N$. There are $Q$ queries, each queries will be in the form ...
0
votes
1answer
401 views

What is the time and space complexity of Rete algorithm

I am working on pattern matching algorithm. Its working and using very less memory. For the comparison, I have to compare it with the Rete Algorithm. I have checked it in the thesis of the author, ...
0
votes
2answers
1k views

Running time with while loop

What's the running time of: foo(n) if(n==1) return; int i=1; while(i<n) { i=i+2 } foo(n-2) There are $n/2$ recursive calls to ...
3
votes
1answer
2k views

Why is a sequence of n Push, Pop, Multipop operations O(n²)?

From "Introduction to Algorithms" by Cormen, Leiserson, Rivest, Stein, Third Edition, page 453: Let us analyze a sequence of $n$ Push, Pop, Multipop operations on an initially empty stack. The ...
5
votes
5answers
1k views

Why call it 'Time Complexity'?

P.S. I have added the tag 'history', if there is any historical connotation. Also, I found this question What is running time of an algorithm? but I am not satisfied with answers.
0
votes
1answer
173 views

Psedu-polynomial Time : Conflict with the definition of input size

From wikipedia In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the length of the input (the number of bits required ...
0
votes
0answers
41 views

What kind of runtime behavior should we expect of Finite Element Methods?

For a typical finite element algorithms, what kind of order of growth in solution time (i.e solve stiffness matrix & post-processing) are we expected to see with an increase in number of elements? ...
0
votes
1answer
79 views

Theta Manipulation to show $N = \Theta(n/\log N)=\Theta(n/\log n)$

I am studying different models of computation and how algorithms can be interpreted under different models. Here is a math(?) question that has been bugging me. Suppose we have $n = \Theta(N\log N)$ ...
0
votes
1answer
344 views

Finding the average time complexity for a max algorithm

I'm trying to find the average-case number of times that max is assigned a value by the below algorithm find_max. ...
2
votes
0answers
81 views

Examples of context-free grammars with worst-case complexity

What are some examples of context-free grammars that necessarily trigger cubic worst-case complexity for GLR parsers? I have seen a mention of the example S $\rightarrow$ SSS | SS | "a" but I would ...
2
votes
1answer
590 views

Recursive functions from O(n) complexity to O(log n)

For some recursive questions that require recursing on an input with a small piece removed (hence linear in the size of the input), can we reduce run time by recursing on two halves of the input each ...
0
votes
2answers
104 views

Good reference for average-case runtime analysis of QuickSort

I'm a beginner in programming with little knowledge about the technicalities. I'm assigned to do a "reading project" on the average case analysis of quicksort. I mean I have to present it in class. ...
35
votes
2answers
10k views

Why is the log in the big-O of binary search not base 2?

I am new to understanding computer science algorithms. I understand the process of the binary search, but I am having a slight misunderstanding with its efficiency. In a size of $s = 2^n$ elements, ...
2
votes
1answer
45 views

Finding running time

Apologies for this simple question. I found it in the book Algorithms by Sedgewick and Wayne. Give a formula to predict the running time of a program for a problem of size N when doubling experiments ...
0
votes
0answers
89 views

Linear time reduction equivalence

I have to show if the following statement is true or false. Suppose we have two problems $A$ and $B$. We want to know whether the following is true: If $A \le_p B$ and there is an algorithm which ...
1
vote
2answers
190 views

Worst Case Scenario in MaxHeapify

First - I've seen and thoroughly read all the similar questions. None of them solves my problem. I've read them all, and seen lectures and asked my Prof but no one was able to answer. They all at most ...
0
votes
0answers
152 views

What would Dijkstra's shortest path algorithm complexity be with the following data structure?

Considering $n$ number of pieces of data, what would Dijkstra's shortest path algorithm time complexity be if it was stored using a data structure with following properties? • delete the record ...
2
votes
0answers
382 views

One algorithm for turnpike reconstruction problem?

In << Data Structure and Algorithm Analysis >>, turnpike reconstruction problem is given for demo of backtracking. Suppose we are given n points, p1 , p2 , . . . , pn , located on the X -axis. ...
3
votes
2answers
97 views

Worst time complexity for finding a median number for a list and array data structure

This was a question that came up in a past exam paper in my computer science course, it states: "There are two simple, un-optimised sorted data structures, each storing n numbers. The first is a list;...
0
votes
0answers
86 views

What is the run time of this algorithm?

Robot in a grid: Imagine a robot sitting on the upper left corner of a grid with $r$ rows and $c$ columns. The robot can only move in two directions, right or down, but certain cells are off limits ...
5
votes
4answers
996 views

Is there really a $ O(1/n) $ algorithm?

What kind of algorithm can have $O(1/n)$ complexity, where $n$ is a natural number? Or, is there any algorithm that the time it takes decreases when the data input increases?
5
votes
1answer
96 views

What is the runtime of the 'Risch Algorithm'?

I have been trying to find the upper bound on the runtime of the 'Risch algorithm' used for finding the integral of mathematical functions, but have been unable to do so. https://en.wikipedia.org/...
0
votes
0answers
184 views

Run time analysis of a program with nested for loops

Problem Let's say we are given a program and we want to find an algorithm that analyses its asymptotic complexity. This program can only have two types of statements: ...
-1
votes
2answers
2k views

Time complexity of searching an element in Binary Search Tree [closed]

I want to know what will be the time complexity to search, insert and delete an element in a) balanced binary search tree. b) unbalanced binary search tree.
3
votes
2answers
3k views

How do we derive the runtime cost of Karatsuba's algorithm?

I've read the Wikipedia article explaining the complexity analysis of the Karatsuba algorithm, but I'm not fully grasping it. I seem to have gotten about 75% of the way to the solution on my own, but ...
5
votes
1answer
14k views

Best-Case Running Time For Binary Search Tree Insertion

The notion of best-case running time is kind of ambiguous for me. According to wikipedia, the definition of best case running time is: The term best-case performance is used in computer science to ...
-2
votes
1answer
317 views

How to get O(Big-oh) notation for following Code [duplicate]

What i came up with is this 1) inner loop goes to 2n and at each. step it increments n/3 times threfore 2log n times it will execute 2) outer goes to n incrementing by 1 threfore n times Hence for ...