Nested for-loop complexity

This is what I got:

Growth:

1. O(log(sqrt(N)))
2. O(N)
3. O(N)
4. O(log(sqrt(N)!)) = O(sqrt(N)*log(sqrt(N))) using Stirling's approximation

Exact numbers: ([X] is the integer part of X)

1. [log([sqrt(N)])]+1
2. 2^([log(N)]+1)
3. [sqrt(N)]*[sqrt(N)+1]/2
4. not really sure.

And here's a little check: I implemented the for loops with a counter, this is the output for N=10000000:

a(N)= 12           a(10*N)= 14
b(N)= 16777216     b(10*N)= 134217728
c(N)= 5000703      c(10*N)= 50005000
d(N)= 33861        d(10*N)= 123631

EDIT: as requested, explanations
First of all, some consideration:

• we are treating integers, so of any real function you see (sqrt and log basically) you should actually take the integer part.
• as almost always in computer science, log = log base 2

Now:

1. i goes from 1 to sqrt(N), but it does so "using" only powers of 2. There are log(M) (+1 actually) powers of 2 between 1 and M, so with M = sqrt(N) you get the formula.

2. i goes from 1 to N by powers of 2, as before. For every i there are i js. If we sum the js for every i:
   1 + 2 + 4 + 8 + 16 + ... + 2^log(N) = 2N - 1 = O(N)

3. i goes from 1 to sqrt(N). For each i, there are i js. As before we sum the number of js for each i:
   1 + 2 + 3 + 4 + 5 + ... + sqrt(N) = sqrt(N) * sqrt(N+1) / 2 = O(N)

4. i goes from 1 to sqrt(N). For every i, j goes from 1 to i using only powers of 2, therefore for every i you have log(i) js. If you sum all the js for every i you get:

   log(1) + log(2) + log(3) + log(4) + log(5) + ... + log(sqrt(N))
   For the property of logarithms log(a) + log(b) = log(a*b). Apply this to our summation:
   log(1*2*3*4*5*..*sqrt(N)) = log( sqrt(N)! )
   Which is the result. Given that the factorial is a problem for large numbers, you can use Stirling's approximation: ln(N!) -> N*log(N) - N for large numbers.

Example of the difference using integer part

Consider 2. The integer part of log(N) stays the same until N doubles. Which means, for example, that this for cycle execs the same number of operations (131072) for N=65536 and for N=131071. When N becomes 131072 (just one more), the number of operations doubles (262144).

You can formally solve the code fragments using Sigma Notation:

a)

b)

c)

d)