-1
$\begingroup$

Is the time complexity of for(int i=0;i<n;i++){i*=k;} $O(\log_k n)$?

The problem is number 8 from GeeksForGeeks:
https://www.geeksforgeeks.org/practice-questions-time-complexity-analysis/

I trace the program by hand and got stuck. I could not prove that the answer is $O(\log_k n)$. I made a mistake somewhere.

Assume $k = 1$ and $n = 3$:

n iteration i = i * k k = 1
0 i = 0 * 1 = 0 1
i ++
1
1 i = 1 * 1 = 1
i ++
2
2 i = 2 * 1 = 2
i ++
2 + 1 = 3

The loop will stop because $i$ is no longer less than $n$.

In general, if $k$ is not known the loop will continue until $i > n$ or $i = n$

What is $i$ if $k = 1$

$i = 0, 1, 2, 3, 4, 5, \cdots, = i + 1$

Replacing $i$ with $k$

$i = 0, 1, 2, 3, 4, 5, \cdots, = k + 1$

$i = k + 1$

Substituting the value of $i$ into the equation $i = n$

$k + 1 = n$

$k = n - 1$

$\log_k (k) = \log_k (n - 1)$

$1 = \log_k (n - 1)$

$T(n) = \log_k (n - 1)$

$\endgroup$
3
  • $\begingroup$ @HereToTryHelp I really appreciate your efforts to edit the question, with 10 edits! Have an upvote. $\endgroup$ Feb 5 at 15:10
  • $\begingroup$ I've edited your question, please review it, and hope you can learn from it next time $\endgroup$ Feb 6 at 0:36
  • 1
    $\begingroup$ @KennethKho, Thank you for taking the time out of your day to edit this question! You could have been doing something else with your time. So, thank you! I am sorry I have taken a long time to get back to you. $\endgroup$ Feb 15 at 13:41

2 Answers 2

0
$\begingroup$

If k=0 then i is set to 0 inside the loop, so it halts instantly if n <= 1 and runs forever otherwise.

If k=1 then the multiplication has no effect. The loop ends instantly if n <= 0 and after n iterations otherwise.

Let m be the number of iterations starting with m = 0. If k >= 2 then i is set to 0 inside the loop during iteration #0, and to a value i >= k^m during iteration #m. So the loop runs at most as long as k^m < n or m < log_k(n).

$\endgroup$
1
  • $\begingroup$ Thank you very much for your explanation! $\endgroup$ Dec 27, 2023 at 21:34
1
$\begingroup$

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 work out the first few iterations and see:

Iteration #$1$: $i = 1 + 0k = 1$

Iteration #$2$: $i = 1 + 1k = 1 + k$

Iteration #$3$: $i = 1 + (1 + k)k = 1 + k + k^2$

Iteration #$4$: $i = 1 + (1 + k + k^2)k = 1 + k + k^2 + k^3$

Iteration #$5$: $i = 1 + (1 + k + k^2 + k^3)k = 1 + k + k^2 + k^3 + k^4$

Iteration #$x$: $i = 1 + k + k^2 + k^3 + \cdots + k^{x - 1} = (k^x - 1) / (k - 1)$

Now we want to solve $x$ for any given $n \in \mathbb{Z}$.

$(k^x - 1) / (k - 1) = n$

$(k^x - 1) = kn - k$

$k^x = kn - k + 1$

$x = \log_k(kn - k + 1)$

$T(n) = O(\log_k n)$

If we don't assume $k > 1$, observe that multiplication by zero will induce infinite loop, and multiplication by one will do nothing, yielding $T(n) = \begin{cases} O(\infty) & \text{if } \lvert k\rvert = 0, k \in \mathbb{Z}\\ O(n) & \text{if } \lvert k\rvert = 1, k \in \mathbb{Z}\\ O(\log_k n) & \text{if } \lvert k\rvert > 1, k \in \mathbb{Z}\\ \end{cases}$

$\endgroup$
9
  • $\begingroup$ Hi @kenneth-kho, Thank you so much for taking the time to write the answer. Thank you for the amount of detail you have put into your answer. Writing the equivalent code was the key to my understand. Question, when you set (k^x -1)/(k-1) = n, is n the point in the loop where i is greater than or equal to n? Question, I do not understand why multiplying by zero will induce infinite loop, and multiplication by one with do nothing. Where are you inputting the values of 0 and 1? I inputted the values of 0 and 1 into log base k of (kn -k + 1) and got log base 0 of 1, log base 1 of n. $\endgroup$ Feb 17 at 15:41
  • $\begingroup$ @HereToTryHelp You're welcome. Answer to question 1: x is the point in the loop where i is greater than or equal to n. Answer to question 2: since log_k (kn - k + 1) is only valid for k > 1, the formula is invalid here, notice with k = 0, the code becomes for(int i=0;i<n;i=1), and notice with k = 1, the code becomes for(int i=0;i<n;i++), try to convince yourself by plugging k into for(int i=0;i<n;i=1+i*k). $\endgroup$ Feb 17 at 15:57
  • $\begingroup$ Hi @kenneth-kho, thank you for taking the time to answer my questions. I finally understand your answers. Thank you! $\endgroup$ Feb 24 at 13:38
  • $\begingroup$ Hi @kenneth-kho, how can I learn how to solve problems like you? How did you learn if I may ask? $\endgroup$ Feb 24 at 13:41
  • $\begingroup$ @HereToTryHelp I appreciate the answer has been accepted. If you have not been fluent with loops, arrays, recursions, practice with questions. Trace the problem by hand just like what we did, but the solution has to be systematically observed and deduced. Understand that everyone that has made it has gone through this, it is a slow process, but it is the only way, and it is totally doable if you give it time. Once you are more fluent, you can start learning algorithms and data structures (CP4 book) and use them. Once you are fluent with that too, you can start learning really creative stuff. $\endgroup$ Feb 24 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.