Let's look at this one. I'm going to ignore the swap for now.
Iteration2:
public static long dominoes(long x, long y){
long temp;
double koeficient = 0, faktor;
for(long i=0; i<=x+y; i++){
koeficient = 1;
for(int j=1; j<y+1; j++){
faktor = ((double)((i+1)-j)) / (double)j;
faktor = koeficient * faktor;
koeficient = faktor;
}
}
return (long)koeficient;
} Let's add annotations, giving the cost of each line.
public static long dominoes(long x, long y){
long temp; // O(1)
double koeficient = 0, faktor; // O(1)
for(long i=0; i<=x+y; i++){
// an O(1) cost for (i <= x+y) and (i++)
koeficient = 1; // O(1)
for(int j=1; j<y+1; j++){
// an O(1) cost for (j < y+1) and (j++)
faktor = ((double)((i+1)-j)) / (double)j; // O(1)
faktor = koeficient * faktor; // O(1)
koeficient = faktor; // O(1)
}
}
return (long)koeficient; // O(1)
} When we have successive statements with cost O(x) and O(y), their combined cost is O(x + y). Let's first remove the pieces of code that we've accounted for.
public static long dominoes(long x, long y){
// O(1)
// O(1)
for(long i=0; i<=x+y; i++){
// O(1)
// O(1)
for(int j=1; j<y+1; j++){
// O(1)
// O(1)
// O(1)
// O(1)
}
}
return; // O(1)
}
You'll note that the lines of code don't modify i or j. If there was some line that said "i = i * i", we wouldn't want to delete that because it would affect the number of iterations of the loop.
Now let's combine successive statements.
public static long dominoes(long x, long y){
// O(2)
for(long i=0; i<=x+y; i++){
// O(2)
for(int j=1; j<y+1; j++){
// O(4)
}
}
return; // O(1)
}
I've written O(2) and O(4) for didactic purposes -- really we'd just write O(1) since O(2) and O(1) are the same thing.
public static long dominoes(long x, long y){
// O(1)
for(long i=0; i<=x+y; i++){
// O(1)
for(int j=1; j<y+1; j++){
// O(1)
}
}
return; // O(1)
}
Now let's look at the inner loop. Its body takes O(1) time. It runs y iterations. So the running time is O(y)*O(1) = O(y).
public static long dominoes(long x, long y){
// O(1)
for(long i=0; i<=x+y; i++){
// O(1)
// O(y)
}
return; // O(1)
}
Now O(1) + O(y) = O(y) so we can combine those successive costs.
public static long dominoes(long x, long y){
// O(1)
for(long i=0; i<=x+y; i++){
// O(y)
}
return; // O(1)
}
Now the outer loop runs x+y times. The interior costs O(y) time. So the cost of the loop is O(x+y) * O(y) = O((x+y)*y).
public static long dominoes(long x, long y){
// O(1)
// O((x+y)*y)
return; // O(1)
}
And O(1) + O((x+y)*y) + O(1) = O((x+y)*y).
public static long dominoes(long x, long y){
// O((x+y)*y)
}
And we're done.
Ignoring the swap that we decided to ignore, the cost is O((x+y)*y). But the truth is that after the swap, if it happens or not, the variable x will contain the minimum of the x and y parameters, and y will contain the maximum. So, accounting for the swap, the running time is O((min(x,y) + max(x,y)) * max(x,y)).
Are we done? We could be. But it's useful to simplify our answer. Note that 1*max(x,y) <= (min(x,y) + max(x,y)) <= 2*max(x,y). Therefore, max(x,y)^2 <= (min(x,y)+max(x,y))*max(x,y) <= 2*max(x,y)^2.
So (min(x,y)+max(x,y))*max(x,y) is Theta(max(x,y)^2) (which is a way to say the two functions are O of one another). This means we can say our function is O(max(x,y)^2) without losing any information.
Like, we could say our function is O(max(x,y)^3), and we'd lose information -- because it's a weaker bound. The fact that (min(x,y) + max(x,y))*max(x,y) is Theta(max(x,y)) means that O(max(x,y)^2) is as strong a bound.
Marked Solved 
Offline 
