The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
27 views

Complexity of the Euclidean algorithm

I have a doubt about the complexity of the Euclidean algorithm; the slide of my Professor says: The calculation of $\mathrm{GCD} (a, b)$ stops at the most after $2\log_2 a$ iterations. (1) Since ...
5
votes
1answer
65 views

How does one end up with a non-integer exponent in time complexity? (e.g., $O(n^{2.81})$)

Periodically I come across sentences like "Winograd's variant [20] of this algorithm, whose asymptotic complexity is also $O(n^{2.81})$ are considered" (from ...
0
votes
0answers
55 views

Reduction from Steiner tree to minimum set cover

I am trying to teach myself complexity. I am trying to come up with a reduction from minimum set cover (given a set of items I, and a set S of subsets of I and an integer k, is there a subset S' of S ...
1
vote
0answers
35 views

What will be the complexity of the function having two input sizes? [closed]

What will be the complexities in the following case: T(m,n) = T(m-1,n) + T(n-1,m) + O(m*n) After a bit of searching I found that if I could make this function monotonic and then try to find the ...
1
vote
7answers
240 views

Checking if there are 2 elements in an array that sum to X in O(n lg n)

I have thought about the most useful way of checking an array for 2 elements that sum to X. The trivial solution is to check the sum of every element with every element, and the complexity of this ...