Algorithmic big o order of growth code

Question

I'm doing an online course and i'm stuck on this question. I know there are similar questions but they don't help me.

What is the order of growth of the worst case running time of the following code fragment as a function of N?

int sum = 0;
for (int i = 0; i*i*i < N; i++)
    for (int j = 0; j*j*j < N; j++)
        for (int k = 0; k*k*k < N; k++)
            sum++;

I thought that the order would be n^3 but I don't think this is correct because the loops only go through a third of n each time. So would that make it nlogn?

Also

int sum = 0;
for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
        for (int k = 1; k <= N; k = k*2)
            for (int h = 1; h <= k; h++)
                sum++;

I think this one would be n^4 because you have n * n * 0.5n * 0.5n

Answer 1

The loops in fact only go up to the cube root of N. (i^3 < n, etc.)

The 3 nested loops of this length, give O(cube root of N, cubed). This O(N)

Of note, if you were correct and they each went to one third of N, then cubing this still gives O(N^3/9), 1/9 is constant, so this is O(n^3)

Answer 2

If you examine the value of sum for various values of N, then it becomes pretty clear what the time complexity of the algorithm is:

#include <iostream>

int main()
{
  for( int N=1 ; N<=100 ; ++N ) {
    int sum = 0;
    for (int i = 0; i*i*i < N; i++)
      for (int j = 0; j*j*j < N; j++)
        for (int k = 0; k*k*k < N; k++)
          sum++;
    std::cout << "For N=" << N << ", sum=" << sum << '\n';
  }
  return 0;
}

You can then draw your own conclusions with greater insight.