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?

Answer 1

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)

Answer 2

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