1

I had the simple problem :

the top level of the pyramid must consist of 1 cube, the second level must consist of 1 + 2 = 3 cubes, the third level must have 1 + 2 + 3 = 6 cubes, and so on. Thus, the i-th level of the pyramid must have 1 + 2 + ... + (i - 1) + i cubes.

What is the maxmum height possible given n cubes.

I coded easily the following solution and passed : 

int main()
{
    int i,sum,n;

    cin >> n;

    i = 1;
    sum = 0;
    while(sum <= n)
    {
        sum = sum + (i*(i+1))/2;
        i++;
    }
    cout << i-2;
    return 0;
}

But, I am not confident on the complexity of this solution. Shall it be O(log n) or something else. I asked a similar question, where I had the same confusion. Can anyone please explain some brief general theory in such cases, such that it covers all such scenarios. Or a link to some good tutorial will be really helpful

Community
  • 1
  • 1
Naveen
  • 7,944
  • 12
  • 78
  • 165
  • If the total number of cubes `n` for i-level pyramid is given by [`n = (i * (i + 1)) / 2`](https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF), then you just [solve for i in that equation](https://www.wolframalpha.com/input/?i=n+%3D+%28i+*+%28i%2B1%29%29%2F2+for+i), no? – Dan Mašek May 15 '16 at 08:35
  • DanMašek is correct. i is O(sqrt(n)). – Abhishek Bansal May 15 '16 at 08:45
  • 1
    @DanMašek you've misread the code. The loop doesn't stop when i(i+1)/2 >= n, it stops when sum >= n. You can solve it in O(1) if you solve the implicit cubic, but solving cubics isn't as easy as solving quadratics. – Paul Hankin May 15 '16 at 08:51
  • @Paul Yeah, i just noticed. – Dan Mašek May 15 '16 at 08:52

1 Answers1

0

You're finding the largest k such that sum(i(i+1)/2 for i = 1..k) <= n.

The sum is Theta(k^3) (see https://en.wikipedia.org/wiki/Pyramidal_number) , so the largest k will be Theta(n^(1/3)).

Since your loop iterates k times, the code is Theta(n^(1/3)).

Paul Hankin
  • 54,811
  • 11
  • 92
  • 118