How to compute the complexity of this?

Question

int foo(int n)
{
    int sum = 0;
    for(int k=1; k <= n; k = k * 2) 
    {
        sum += k;
    }
    return sum;
}

I have the following function. Now, according to me the runtime complexity of foo(n) should be big-o(logn). Now, I am asked to find out the run time complexity of foo(n*n*n*n). What should it be? According to me, it should be, big-o(logn) only. Am I right in saying this?

I am asked to find out the run time complexity of foo(nnn*n).What does it means? — Avinash
– Avinash, Commented Sep 15, 2014 at 7:16
What is the reason of donwvoting the question, I don't understand? — Qirohchan
– Qirohchan, Commented Sep 15, 2014 at 7:22

Paul R · Accepted Answer · 2014-09-15 07:20:02Z

4

It is O(log n⁴) → O(4 log n) → O(log n)

answered Sep 15, 2014 at 7:20

Paul R

214k38 gold badges402 silver badges579 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Qirohchan Over a year ago

Yes, I did it by that way only. Thanks. :)

Maroun · Accepted Answer · 2014-09-15 13:16:17Z

4

Ask yourself, how many times does the loop execute? Create a table for the loop when the input is n:

for(int k=1; k <= n; k = k * 2)

  Iteration  |  k 
-------------+-----
      1      |  1
      2      |  2
      3      |  4
     ...     | ...
     ...     | ...
      k      |  n

2^k = n → k = log(n)

Now you're asking for n⁴ input. Simply change the table to:

  Iteration  |  k 
-------------+-----
      1      |  1
      2      |  2
      3      |  4
     ...     | ...
     ...     | ...
      k      | n^4

2^k = n⁴ → k = log(n⁴) = 4 * log(n)

edited Sep 15, 2014 at 13:16

answered Sep 15, 2014 at 7:15

Maroun

96.3k30 gold badges195 silver badges249 bronze badges

10 Comments

Maroun Over a year ago

@PaulR I'm giving OP a direction, not a full solution. I think my example should guide him to reach the answer.

Paul R Over a year ago

He's already solved this part - read the whole question carefully.

Qirohchan Over a year ago

I think it will be 8 corresponding to 3. However, it will be big-o(logn) for n^4 as well, right?

Paul R Over a year ago

All good now - have an up-vote - sometimes the simplest questions can be the fiddliest! ;-)

Ankur Agarwal Over a year ago

Please note that the value of k after iteration i is actually 2^(i-1). So if k becomes equal to n after i iterations then the loop ran for i times which is the complexity of the code. 2^(i-1) = n, and now you can solve this for i.

|

Collectives™ on Stack Overflow

How to compute the complexity of this?

2 Answers 2

1 Comment

10 Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

10 Comments

Related