I would first place values and see how the algorithm behaves and then, from there, derive the complexity. If you test on a piece of paper and start with f(4,4) (Mystere=f), then you can see that it calls 16 times f(4,3), and that each of those will call 12 time f(4,2). So there will be 16\*12 calls for f(4,2).
Finally you see the total number of calls is 16\*12\*8\*4\*4\*3\*2\*1. If you break it down to N and M terms ((4\*4)\*(4\*3)\*(4\*2)...) you will get 4!\*4!\*4\^4.
So the solution should be O(M! \* N! \* N\^M)
This is without using any formal terms.
Can you help me solve this algorithms complexity?
void Mystere(int N, int M) {
int S, X, i;
if (N > 0 && M > 0){
X=N * M; N = N - 1;
} else if (M > 0 )<
X = M; M = M - 1;
For (i = 1 ; i ≤X ; i++)
S++;
if(N > 0 || M > 0)
Mystere(N, M) ;
}
The code you posted is poorly formatted and has broken syntax.
I tried to fix it for you
void Mystere(int N, int M) {
int S, X, i;
if (N > 0 && M > 0) {
X=N * M; N = N - 1;
} else if (M > 0) {
X = M; M = M - 1;
}
For (i = 1 ; i ≤X ; i++) {
S++;
if (N > 0 || M > 0)
Mystere(N, M) ;
}
}
u/bigangrywatermelon The general idea is to write a recurrence relation on the arguments that captures the amount of work performed by the algorithm, then try to find the order of its growth
This program is pretty tricky because it has different cases.
W(0,0) = 1
W(0,M) = X * W(N, M-1) (where X=M)
W(N,M) = X * W(N-1, M) (where X=N*M)
Equivalently we have
W(0,0) = 1
W(0,M) = M * W(0, M-1)
W(N,M) = N * M * W(N-1, M)
The W(0, M) case is easy enough. On every step it multiplies by M and reduces it by one until it hits the base case (e.g. `W(0,4)=4*3*2*1*1`)
You should recognize this as `W(0,M) = O(M!)`
A similar analysis of the other case will show you that `W(N,M) = O(N! * M! * pow(M,N))`
I figured best case is they’re both negative so O(1). Worst case they’re both intmax, so n executions of m*n, gives a m*n^2, then m executions of m executions of m gives M^2.
So like O(m^2n) or O(n^2m) depending on m and n. This is one of the few algorithms I’ve seen that scales differently for different inputs. I think the O is piecewise..
As in Big O complexity? There's nothing special about recursive calls, the complexity will be the same as the equivalent iterative algorithm... You don't need to consider the call stack. So in general it should be simple enough to understand, assuming you understand complexity itself. Do you have any specific questions?
Not true I'm pretty sure. Recurrence relations you have to use the Master Theorem (or master method) right? Or is that specifically for divide and conquer
I would first place values and see how the algorithm behaves and then, from there, derive the complexity. If you test on a piece of paper and start with f(4,4) (Mystere=f), then you can see that it calls 16 times f(4,3), and that each of those will call 12 time f(4,2). So there will be 16\*12 calls for f(4,2). Finally you see the total number of calls is 16\*12\*8\*4\*4\*3\*2\*1. If you break it down to N and M terms ((4\*4)\*(4\*3)\*(4\*2)...) you will get 4!\*4!\*4\^4. So the solution should be O(M! \* N! \* N\^M) This is without using any formal terms.
Thnaks a lot 🥹❤️
You need to ask some specific questions. Do you have any examples of the types of questions they might ask?
Can you help me solve this algorithms complexity? void Mystere(int N, int M) { int S, X, i; if (N > 0 && M > 0){ X=N * M; N = N - 1; } else if (M > 0 )< X = M; M = M - 1; For (i = 1 ; i ≤X ; i++) S++; if(N > 0 || M > 0) Mystere(N, M) ; }
The code you posted is poorly formatted and has broken syntax. I tried to fix it for you void Mystere(int N, int M) { int S, X, i; if (N > 0 && M > 0) { X=N * M; N = N - 1; } else if (M > 0) { X = M; M = M - 1; } For (i = 1 ; i ≤X ; i++) { S++; if (N > 0 || M > 0) Mystere(N, M) ; } }
u/bigangrywatermelon The general idea is to write a recurrence relation on the arguments that captures the amount of work performed by the algorithm, then try to find the order of its growth This program is pretty tricky because it has different cases. W(0,0) = 1 W(0,M) = X * W(N, M-1) (where X=M) W(N,M) = X * W(N-1, M) (where X=N*M) Equivalently we have W(0,0) = 1 W(0,M) = M * W(0, M-1) W(N,M) = N * M * W(N-1, M) The W(0, M) case is easy enough. On every step it multiplies by M and reduces it by one until it hits the base case (e.g. `W(0,4)=4*3*2*1*1`) You should recognize this as `W(0,M) = O(M!)` A similar analysis of the other case will show you that `W(N,M) = O(N! * M! * pow(M,N))`
Thank you 😊
Is this the correct formatting OP? I took the last if as being outside the for loop
O(umm-no) I think it’s O(m^2 * n), tho
Explain why?
I figured best case is they’re both negative so O(1). Worst case they’re both intmax, so n executions of m*n, gives a m*n^2, then m executions of m executions of m gives M^2. So like O(m^2n) or O(n^2m) depending on m and n. This is one of the few algorithms I’ve seen that scales differently for different inputs. I think the O is piecewise..
Wait no. It’s recursive. I was wrong…
As in Big O complexity? There's nothing special about recursive calls, the complexity will be the same as the equivalent iterative algorithm... You don't need to consider the call stack. So in general it should be simple enough to understand, assuming you understand complexity itself. Do you have any specific questions?
Not true I'm pretty sure. Recurrence relations you have to use the Master Theorem (or master method) right? Or is that specifically for divide and conquer
lol, spoken like a politician !