Find the time complexity of the function "foo"

Question

I'm struggling to find the time complexity of this function:

void foo(int n) {
    int i, m = 1;
    for (i = 0; i < n; i++) {
        m *= n; // (m = n^n) ??
    }
    while (m > 1) {
        m /= 3;
    }
}

Well, the first for iteration is clearly O(n^n), the explanation to it is because m started with value 1, and multiplies itself n times.

Now, we start the while loop with m = n^n and we divide it every time by 3. which means, (I guess), log(n^n).

Assuming I got it right up till now, I'm not sure if I need to sum or multiply, but my logic says I need to sum them, because they are 'odd' to each other.

So my assumption is: O(n^n) + O(log(n^n)) = O(n^n) Because if n is quite big, we can just refrain from O(log(n^n)).

Well, I really made many assumptions here, and I hope that makes sense. I'd love to hear your opinions about the time complexity of this function.

But the loop still goes n times in the first one so it is O(n) — camel-man, Feb 10 '16 at 21:53
@camel-man Oh right, and btw, O(n) > O(log(n^n))? if yes, why? — Ilan Aizelman WS, Feb 10 '16 at 21:54
The size of `n` is limited in C, the function will have undefined behavior for all but very small values of `n`. — chqrlie, Feb 10 '16 at 22:00

score 2 · Accepted Answer · edited Feb 11 '16 at 00:16

2

Theoretically, time complexity is O(n log n) because:

for (i=0; i<n; i++) 
   m *= n;

this will be executed n times and in the end m=n^n

Then this

while (m>1)
   m /= 3;

will be executed log3(n^n) times which is n * log3(n):

P.S. But this is only if you count number of operations. In real life it takes much more time to calculate n^n because the numbers become too big. Also your function will overflow when you will be multiplying such big numbers and most probably you will be bounded by the maximum number of int (in which case the complexity will be O(n))

edited Feb 11 '16 at 00:16

chqrlie

131,814
10
121
189

answered Feb 10 '16 at 21:55

Salvador Dali

214,103
147
703
753

Assuming I'm not bound by maximum number, the answer will be n * log3(n) = O(n * log(n)) right? – Ilan Aizelman WS Feb 10 '16 at 22:11
1

@IlanAizelmanWS yes, but then it can't be written in c in a way you wrote it. – Salvador Dali Feb 10 '16 at 22:16
I see. Thank you very much for your time and effort you put here sir. – Ilan Aizelman WS Feb 10 '16 at 22:17

chux - Reinstate Monica · Answer 2 · 2016-02-10T22:45:37.233

With foo(int n) and 32-bit int, n cannot exceed the magnitude of 10, else m *= n overflows.

Given such a small range that n works, the O() seems moot. Even with 64-bit unsigned m, n <= 15.

So I suppose O(n lg(n)) is technically correct, but given the constraints of int, suspect code took more time to do a single printf() than iterate through foo(10). IOWs it is practically O(1).

unsigned long long foo(int n) {
  unsigned long long cnt = 0;
  int i;
  unsigned long long m = 1;
  for (i = 0; i < n; i++) {
    if (m >= ULLONG_MAX/n) exit(1);
    m *= n; // (m = n^n) ??
    cnt++;
  }
  while (m > 1) {
    m /= 3;
    cnt++;
  }
  return cnt;
}

And came up with

Find the time complexity of the function "foo"

2 Answers2