How to calculate 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, in my opinion, the complexity of executing foo (n) should be big-o (logn). Now I was asked to find out the runtime complexity of foo (n * n * n * n). What should it be? For me, it must be big-o (logn). Am I saying it right?

Answer 1

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

Answer 2

Ask yourself, how many times does the cycle run? Create a table for the loop when the input 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)

n ⁴. :

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

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