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.