rsonx

### Questions (14)

 1 Difficulty understanding the use of arbitrary function for the worst case running time of an algorithm 1 Worst case running time of lexicographical sorting of a list of n strings each of length n using merge sort 1 Can there be a language not Context free but still PDA acceptable? 1 Why is $T(n)=3T(n/4) + n\log n$ solvable with Master Method but $T(n)=2T(n/2) + n\log n$ is not? 1 How to mathematically prove that a relation T(n)=T($\sqrt{n}$)+c is O(log(log(n))?

### Reputation (245)

 +10 Difficulty understanding the use of arbitrary function for the worst case running time of an algorithm +20 Do you ever “download” a language? +10 Worst case running time of lexicographical sorting of a list of n strings each of length n using merge sort +10 Can there be a language not Context free but still PDA acceptable?

 2 Do you ever “download” a language? 2 Prove if $L = \{0^m1^n \mid m \neq n\}$ is regular or not 0 Little O notation relationship

### Tags (26)

 2 automata × 5 2 compilers 2 pumping-lemma × 2 2 programming-languages 2 finite-automata × 2 0 time-complexity × 6 2 computability 0 asymptotics × 6 2 interpreters 0 runtime-analysis × 4

### Bookmarks (3)

 1 How to mathematically prove that a relation T(n)=T($\sqrt{n}$)+c is O(log(log(n))? 1 Prove if a property of a Turing Machine is decidable or not, how can I do it? 1 How to translate automaton (Turing machine) into the program of high level programming language?