My third post got deleted .... I will just repeat the few points that need to be completed.
If we denote "n" as dimension of the board, then we can see quite easily that there can't be more than n queens placed on the board such that all of them are safe.
Using that fact, it can be shown that the running time for the first method (in the previous post) is also in O(n^2). That follows from the fact that you can't place more than n queens on board of size nxn, while keeping them all safe (so an upper-bound of (4n).n+4n on the running time can easily be established).
If you add the condition that "if(m>n) return false" at the beginning of second method, its running time will also be
in O(n^2) for sure. What if you don't add it? I haven't thought about it fully
In practice, we would add the "if condition" above for both methods at any rate. In that case the second method would be better when m is much smaller than n.
------
Another interesting function is the maximum number of queens(ouput) that can be placed on a board of given dimensions(input), such that all of them are safe. It can be programmed easily, but how efficiently?
edit: corrected a small mistake