Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.

Sign up to join this community

Anybody can ask a question

Anybody can answer

The best answers are voted up and rise to the top

Explore our Questions

Ask Question

more tags

Active 2 Bountied Hot Week Month

1

vote

0

answers

15

views

Configuration of a space bounded turing machine

complexity-theory turing-machines time-complexity automata space-complexity

modified yesterday Yuval Filmus 237k

-1

votes

1

answer

27

views

Time complexity of a machine which combines Insertion Sort and Quicksort

algorithms time-complexity algorithm-analysis sorting quicksort

answered yesterday gnasher729 20.7k

0

votes

1

answer

23

views

Time complexity of a^{n^b}; a,b>1

time-complexity

modified 2 days ago zkutch 769

-1

votes

0

answers

35

views

Recurrence relation $T(n/10) + T(c·n) + n$

complexity-theory time-complexity trees recursion big-o-notation

modified 2 days ago Pål GD 8,601

0

votes

0

answers

39

views

Prove that $T(n)=\omega(n)$?

complexity-theory time-complexity trees recursion big-o-notation

modified Nov 23 at 14:02 user128813 1

0

votes

1

answer

136

views

How to prove the optimization version problem (whose decision version is NP-complete) can be solved in poly-time iff P=NP?

complexity-theory time-complexity optimization np-complete np-hard

modified Nov 22 at 22:05 Alapan Chaudhuri 103

2

votes

1

answer

2k

views

To find median of k sorted arrays of n elements each in less than O(nklog(k))

time-complexity arrays heaps mergesort c++

modified Nov 22 at 13:17 Yuval Filmus 237k

2

votes

2

answers

76

views

Examples of higher order algorithms ($\mathcal{O}(n^4)$ or larger)

time-complexity p-vs-np

modified Nov 21 at 9:08 Community♦ 1

0

votes

0

answers

169

views

+100

Find $k$'th smallest element in matrix with sorted rows

algorithms time-complexity data-structures sorting arrays

modified Nov 20 at 18:09 user355834 1

0

votes

1

answer

43

views

Explanation of pseudocode and time complexity analysis

time-complexity pseudocode

modified Nov 17 at 15:02 zkutch 769

1

vote

1

answer

137

views

Why log-space reduction is used for NL-completeness while PSPACE reduction isn't used for PSPACE completeness?

complexity-theory time-complexity reductions complexity-classes space-complexity

modified Nov 17 at 9:44 Tomer.Ov 23

1

vote

1

answer

39

views

If $f(n) = O(g(n))$ then $\log\lfloor f(n) \rfloor = O(\log \lfloor g(n) \rfloor)$?

algorithms time-complexity

answered Nov 16 at 10:50 Yuval Filmus 237k

3

votes

0

answers

29

views

What's the best non-amortized disjoint set?

time-complexity data-structures disjoint-sets

asked Nov 14 at 23:53 user23013 458

0

votes

1

answer

23

views

Runtime Analysis: What grows faster?

time-complexity

modified Nov 14 at 1:20 xskxzr 6,529

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled