Linked Questions
42 questions linked to/from How to come up with the runtime of algorithms?
0
votes
0
answers
250
views
Implement Immediate Smaller Element problem using Stack
Immediate Smaller Element Problem:
Given an integer array arr of size $n$. For each element in the array, check whether the right adjacent element (on the next ...
- 101
0
votes
2
answers
99
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 ...
- 115
2
votes
1
answer
52
views
Proving complexity of computing product of matrices
If $A$ is a non-singular $n\times n$ matrix, $B$ is an $n\times p$ matrix, and $C$ is a $p\times n$ matrix (where $1\le p \ll n$), how does one prove that the complexity of $$D=A^{-1}(BC)$$ is $\frac{...
- 131
1
vote
1
answer
121
views
Big-O in computer Science [duplicate]
As the title states, I am asking for how the big-O in asymptotic analysis is used in theoretical computer science. It would be helpful if an example would be given.
user13078
0
votes
1
answer
59
views
Reccurrence equation and finding suitable algorithm
I'm given the following recurrence equation:
$$\begin{align*}
T(1) &= 0\\
T(n) &= T(n/2) + 1 && \text{when $n > 1$ is even}\\
T(n) &= T((n+1)/2) + 1 && \...
- 103
0
votes
1
answer
98
views
Understanding time complexity of algorithm to determine if parenthesis are matching
Both these algorithms determine if all the parenthesis in a string are
balanced and properly nested.
The first algorithm uses "a constant amount of memory, regardless of the length of
the string.&...
- 13
0
votes
1
answer
80
views
Converting a algorithm to a runtime function
I need to find an upper limit for the runtime of $f(n)$.
...
- 143
1
vote
1
answer
52
views
How to calculate the basic steps in Fibonacci sequences to get nFn and n^2
I am reading Algorithms by Sanjoy Dasgupta, Umesh Vazirani, Christos Papadimitriou and I am trying to understand how the number of steps $nF_n$ and $n^2$ were calculated. Here's the part of the book ...
- 659
1
vote
0
answers
65
views
Big-Oh of algorithm
I found an algorithm which sorts the digits of a number to its smallest form. IE 54321 ==> 12345.
The algorithm looks like:
...
- 11
0
votes
0
answers
56
views
Time complexity of this for-loop
I know, the inner loop here is O(log n). But, I get confused by the multiplication in the outer loop part.
...
- 125
0
votes
0
answers
31
views
Am I doing this correctly? Recurrence Relations [duplicate]
The function is this:
...
0
votes
0
answers
18
views
Big o notation for the algo [duplicate]
Asked this at programmers Stack Exchange, was recommend to ask here :
What would be the big o for the algo:
for (i=0; i < n*n; i++)
for(j=0; j<i*i; j++)
...
- 1