I'm still new to Data Structure and Algorithm and therefore I would like to ease my doubts. I'm required to find the Big-O running time of myMethod():

 Static int doIt(int n) {
           for 𝑖←1 π‘‘π‘œ 100 do    -> 100
             for π‘˜β†1 π‘‘π‘œ 𝑛 do    -> n x 100
                 𝑗←1;π‘šβ†π‘›       -> 1
           while 𝑗<π‘š do       -> lg n
          π‘šβ†(π‘š+𝑗)/2           -> lg n/2
        end while 
        end for 
        end for

 static int myMethod(int n) {
                  𝑖 ←1
                  π‘€β„Žπ‘–π‘™π‘’ (𝑖 < 𝑛) {          -> lg n
                        π‘‘π‘œπΌπ‘‘(𝑛)            -> ?
                         𝑖←𝑖×2             -> lg n
            π‘Ÿπ‘’π‘‘π‘’π‘Ÿπ‘› 1; 


For each of the line I have inserted the answer I think would be a logical value to put e.g "-> 100". However I am not confident with the answer. These are the following questions that I would like to ask as well:

  1. Does all while loop have a value of lg n?

  2. If the doIt(n) method does not have a return statement, do we still add in part of calculation?

  3. For the line with m <- (m+j)/2, the value I have inputted is lg n /2. Is that correct or is it some other value?

  4. Whenever multiplying by 2 or dividing by 2 is it always lg 2? what if n is multiplied by 3?

Thank You


1 Answer 1

  1. The while loop is executed $O(\log n)$ times (more precisely, $\Theta(\log n)$ times).

  2. Yes. You account for every statement that is executed.

  3. The line can $m \gets (m+j)/2$ can be executed in time $O(1)$, assuming that arithmetic operations take constant time. The overall time spent in one execution of the wile loop of the function doIt(n) is $O(\log n)$, since the number of its iterations is also $O(\log n)$ (and, more precisely, $\Theta(\log n)$).

  4. This depends on the actual cost model you are using. Assuming that arithmetic operations take constant time, what you are probably thinking of is the number of divisions (resp. multiplications) by $2$ needed for $n$ to drop below (become larger than) some value $x < n$ (resp. $x>n$). If that's the case then the number of iterations is $O(\log n - \log x) \subseteq O(\log n)$ (resp. $O(\log x - \log n) \subseteq O(\log x)$. Multiplying/dividing by any constant greater than $1$ does not change the asymptotic time complexity (recall that $\log_b a = \frac{\log_2 a}{\log_2 b}$, where $\log_2 b$ is a constant in this scenario).

  • $\begingroup$ what about i <- i x 2? what I've learned that it's log(n). Is that true? $\endgroup$
    – Veree
    Commented Jul 20, 2020 at 11:56
  • $\begingroup$ There no $n$ in your expression so I'm not sure what you're asking. The time complexity of multiplying a (positive) integer $n$ by $2$ depends on the cost model you're using for your analysis. In the uniform cost model every basic arithmetic operation (such as multiplications) assumed to required $O(1)$ time. In the logarithmic cost model the time required is proportional to the number of bits involved, so the time needed to double $n$ is $O(\log n)$. $\endgroup$
    – Steven
    Commented Jul 20, 2020 at 19:10

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.