title: Time complexity of N Queen using backtracking?
body: <pre><code>#include&lt;stdio.h&gt;
  #include&lt;math.h&gt;
  
  void printboard(int n);
  void fourQueen(int k,int n);
  int place(int k,int i);
  int x[100];
  
  void NQueen(int k,int n)
  {
    int i;
    for(i=1;i&lt;=n;i++)
    {
      if(place(k,i)==1)
      {     x[k]=i;
              if(k==n)
              {
                  printf("Solution\n");
                  printboard(n);
              }
              else
                  NQueen(k+1,n);
      }
    }
  }
  
  int place(int k,int i)
  {
    int j;
    for(j=1;j&lt;k;j++)
    {
      if((x[j]==i)||abs(x[j]-i)==abs(j-k))
          return 0;
    }
    return 1;
  }
  
  void printboard(int n)
  {
    int i;
    for(i=1;i&lt;=n;i++)
      printf("%d  ",x[i]);
  }
  
  void main()
  {
      int n;
      printf("Enter Value of N:");
      scanf("%d",&amp;n);
      NQueen(1,n);
  }
  </code></pre>
  
  <p>I think it has time complexity: O(n^n), As NQueen function is recursively calling, but is there is any tighter bound possible for this program? what about best case, and worst case time complexity. I am also confused about the place() function which is O(k) and calling from NQueen().</p>