New answers tagged

0

Have you run the code? If you reverse the array ['d', 'r', 'a', 'h', ' ', 's', 'i', ' ', 's', 'c'] you get the desired result of ['c', 's', ' ', 'i', 's', ' ', 'h', 'a', 'r', 'd']. If you then reverse the words you get ['s', 'c', ' ', 's', 'i', ' ', 'd', 'r', 'a', 'h'], which is not what you want. You can't get better than an $O(n)$ complexity for ...


1

This algorithm runs in linear time in the size of the input $O(n)$. To see why try to count how many times you read/write to a position in the string. Note that asymptotically this is equal to the total running time.


0

There is no one QuickSort. There is one original, which we only care about for historical reasons, and many variations, all different. In the case of n identical items, different implementations will run in O(n log n) or O (n^2). Since this is a practical case, the latter kind of algorithm should be avoided. Your point (3) is wrong. Worst case for n ...


1

The usual rule here is only one question per post. Link [2] doesn't say that random pivot and median pivot lead to $O(n^2)$ time complexity. The median of first, middle, and last element is not the median of the whole array. Writing "median pivot" is probably a bad idea, unless you have carefully specified what that's a median of. Link [1] says that ...


1

You can compute the average using linearity of expectation. Let the random variable $X$ denote the number of elements that are retained. Let $X_i$ be an indicator r.v. that is 1 if the $i$th element is retained, or 0 otherwise. Then $X = X_1+\dots + X_n$, so $$\mathbb{E}[X] = \mathbb{E}[X_1] + \dots + \mathbb{E}[X_n] = \Pr[X_1=1] + \dots + \Pr[X_n=1].$$ ...


1

Assuming the model of computation is RAM(Random Access Machine). Which means the cost of addition, multiplication,division etc is constant. Now your program is int j = 0; for (int i = 1; i <= n; i *= 2) { j = j + n * 2; } Inside the loop, you are doing addition, multiplication, comparison etc which takes constant time. Let $k$ denotes the number of ...


0

The approach you describe can be implemented to run in linear time. Build a bipartite graph where left-vertices are blocks and right-vertices are packets, and with an edge from block $b$ to packet $p$ if $b$ is one of the blocks xor-ed to create $p$'s message. Store the bipartite graph in adjacency list format. Also keep track of the degree of each packet,...


2

If you look at the code, it is quite obvious that there are exactly fib(N) - 1 additions. Therefore the time complexity is $\Theta(fib(n))$.


Top 50 recent answers are included