# Tagged Questions

92 views

### Please give me an example of the algorithm where $\Theta$ will be equal to $e^n$

Please give me an example of the algorithm where $\Theta$ or $O$ will be equal exactly to $e^n$ . The algorithm should not be simple counting from 0 till $e^n$ . It should be a clear relation of two ...
42 views

### How to find the asymptotic behavior of these sums?

Let $$X(n) = \displaystyle\sum_{k=1}^{n}\dfrac{1}{k}.$$ $$Y(n) = \displaystyle\sum_{k=1}^{n}k^{1/k}.$$ $$Z(n) = \displaystyle\sum_{k=1}^{n}k^{k}.$$ For the first, I don't have a formal proof but I ...
46 views

### Biggest common sub-string search asymptotics

What is the function of Big-O in case where we use brute-force on two strings to find the biggest common sub-string. Please can you explain the underlying logic to the resulting formula corresponding ...
27 views

### Theoretical question of physical analogies to different O(f(x)) based characteristics of algoritms

I want to better understand the following concepts: "n!", "e^n". I.e. what is the physical analogy of the functions at the bottom of the message. F.ex. for the "n^a" and "log a x" where a equals to ...
26 views

243 views

### How to arrange functions in increasing order of growth rate , providing f(n)=O(g(n))

Given the following functions i need to arrange them in increasing order of growth a) $2^{2^n}$ b) $2^{n^2}$ c) $n^2 \log n$ d) $n$ e) $n^{2^n}$ My first attempt was to plot the graphs but it didn't ...
39 views

### Prove that (x+1)! is not O(x!)

Discrete math question which is as follows: Prove that (x+1)! is not O(x!) using only the definition of Big-Oh notation. (Hint!: log(a * b) = (log a + log b)) I used a proof by contradiction saying ...
27 views