## Microsoft Interview Question

**Country:**United States

Complexity of the code can be represented by the formula: [n(n-1)(n-2)]/6

which is O(n^3).

Because inside the inner-most loop the code basically enumerates nC3 or all possible combinations (i,j,k) with three numbers in [1,n]. n(n-1)(n-2) gives you all possible permutations(where 1,2,3 and 3,2,1 counted differently). By dividing it by 3!=6 you count permunations with the same set of numbers only once.

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.

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)

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
!
```

When an algorithm is O(n^3) it doesn't mean that for n=16 it runs exactly 16^3. Especially for small values of n (like n=16) the number is biased by the constants and what you get is not accurate enough to discriminate between O(n^3) or O(n^2) or even some cases O(n)!

You have to consider the growth rate. For example, what happens if n doubles or triples and then measure the increase. This code is O(n^3).

Yes, you are right. I graphed it and it does break back toward O(n^3).

Here was the #s

! node time-complexity

1 0 0

2 0 0

4 4 0.0625

8 56 0.109375

16 560 0.13671875

32 4960 0.1513671875

64 41664 0.158935546875

128 341376 0.16278076171875

256 2763520 0.1647186279296875

512 22238720 0.16569137573242188

1024 178433024 0.16617870330810547

2048 1429559296 0.16642260551452637

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.

- Mohammad August 31, 2014n = 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.