New answers tagged

2 votes

How does knowing the input size make the time complexity of a function constant?

This can be summed up in one sentence that you should memorise: In complexity theory, what we call a "problem" is never one question, but instead an infinite family of questions that depend ...
Stef's user avatar
  • 495
5 votes

Big-O time complexity for this code snippet

You are right, the two innermost loops perform $\Theta(\log n)$ iterations each, so we have a total of $\Theta(\log^2 n)$ iterations, which are repeated $\Theta(n)$ times in the outer loop, which ...
SilvioM's user avatar
  • 808
1 vote

Is the time complexity of a loop that simultaneously increments and multiplies $O(\log_k n)$ when $k = 1$?

In the incomplete GeeksForGeeks question #8, it is only correct when $k > 1, k \in \mathbb{Z}$. The code is equivalent to for(int i=0;i<n;i=1+i*k). We can ...
Kenneth Kho's user avatar
2 votes

Is there a language $L$ such that $L \in DSPACE(1) \setminus DTIME(1)$?

No. Consider the language $$L = \{x \in \{0,1\}^* \mid x \text{ has even parity}\},$$ i.e., $$L = \{x_1 \cdots x_n \mid x_1 + x_2 + \cdots + x_n \equiv 0 \pmod 2\}.$$ This language is in $\textsf{...
D.W.'s user avatar
  • 158k
2 votes
Accepted

Time complexity for logarithmic algorithm

$\sum\limits_{k=1}^{n}\log \frac{n}{k} = \sum\limits_{k=1}^{n}\log n-\sum\limits_{k=1}^{n}\log k = \log n^n - \log n! = n \log n - (n \log n - n + O(\log n)) = n - O(\log n) = O(n)$
Kenneth Kho's user avatar
1 vote

Time complexity for logarithmic algorithm

You need to add log (n / k), not log (n - k). To examine this closer: For values n/2 <= k <= n you have only one iteration of the inner loop. For values n/4 <= k < n/2 you have two ...
gnasher729's user avatar
  • 29.4k

Top 50 recent answers are included