CareerCup

It is certainly O(N^3). If you doubt it replace the inner "// some code" with a c++ to count how many times that line get executed.

n = 1 -> c = 0
n = 2 -> c = 0
n = 4 -> c = 4
n = 8 -> c = 56
n = 16 -> c = 560
n = 32 -> c = 4960
n = 64 -> c = 41664

As you see when n doubles c increases around 8-9 times, so it is a N^3.
The only possibility is that the code in your interview was different.

Complexity of the code can be represented by the formula: [n(n-1)(n-2)]/6
which is O(n^3).

and that's why you should consider again whether you REALLY want to work for microsoft

Simple way to look at this is drop all the "off by one" non-sense. The +1 and -1's don't matter much at scale.

so for N iterations, we run N/2 iterations of N/4 iterations. But when you account for constants getting dropped and such we still get N^3

for (int i = 0; i < n; ++i)
    {
    	//some code
        for (int j = i; j < n; ++j)
        {
        	//some code
        	for (int k = j; k < n; ++k)
        	{
        		//some code
        	}
        }

Yes each loop isn't starting at 0 but it doesn't have to to count. This is very similar to the question of how many contiguous subarrays are there in an array.

There is 3 for loops each loop will take n times. So you think that O(n^3). but when ever considering time complexity we need to consider tightest upper bound which is O(n^2). You cannot go below this time to complete all the three loops.

Definitely this will be O(n^3)

Suppose,

if i=0,
j=1, then some code will execute= n-2
j=2, then some code will execute= n-3
.
.
j=n-1, then some code will execute= n-(n-1)=1
so for i=0, some code will execute = (n-2) + (n-3)+...1 = O(n^2)
so for i=1, like that code execution will be 0(n^2)..
so after executing it n times ... it will be 0(n^3)

it is O(n*n*n). may be interviewer want to distract the person.

I know the code that is put up here looks like an obvious n^3 , however, i dont think we can rule out n^2 completely. I mean there are many graph based dynamic programming algorithms where the efficiency when analysed from the node side is nm or even n^2.
Could you please include the code in the middle ? I mean if there are
continue; statements in the higher recurrence structures as well,
it might help clear it out.

It's not O(n^3) because the # of ops doesn't scale anywhere near n^3 as n increases,
consider `n = 16`, 16^2 = 256, 16^3 = 4096, at n= 16 this algorithm executes only 560 operations (this is more than 256, but is still an order of magnitude lower than O(n^3) so the lower order is O(n^2))

As to why this is the case: the reason is because as `i` iterates the number of `j` loops decreases and as `j` iterates the number of times `k` loops decreases.

If `i`, `j`, `k` were static loops of fixed iteration n then this would be O(n^3)

n = 16
sum = 0
for (i = 0; i < n - 2; i++)
        for (j = i + 1; j < n - 1; j++)
                for (k = j + 1; k < n; k++)
                        sum += 1
console.log(sum)
var sum
, i
, j
, k
, n

! node time-complexity.js
560
!

It should be O(n^2). Since i has n-2 values. j has no value avaliable. k has n-1 values. So finally O((n-2)(n-1)). That is the highest power n^2.