algorithmscomputational complexity
I know the outer while loop runs log(n) times. In the 'for' loop i am having problem. I tried with putting different values of 'n' and then seeing how many times 'for' loop runs , but im not getting a definite answer. For Eg. with n=100 , it runs 13 times, which is neither log(n) nor sqrt(n).
For a loop like this,
for (int i = 5; i < N; i++)
one way to count the number of iterations is to make a list of the number of different
values of $i$ that will occur; each one results in one iteration of the loop.
Those values are
$$ 5, 6, 7, 8, \ldots, N - 1. $$
In case you still don't recognize how many numbers are in that list,
it's almost the same as the list we get for for (int i = 0; i < N; i++), which is
$$ 0, 1, 2, 3, 4, 5, 6, \ldots, N - 1. $$
The difference is that when we start at $i=5$, we skip the first five numbers in the longer list. Those iterations never occur. So instead of $N$ iterations, we have only
$N - 5$ iterations.
Now for this more complicated example:
for (int i = 0; i < N; i++)
for (int j = i+1; j < N; j++)
for (int k = i+1; k < N; k++)
for (int h = k+1; h < N; h++)
In order to get some clue about how many iterations of the inner loop might occur, it can help to try some actual numbers. So if $N = 4,$ for example, the outer loop runs four times, with values of $i$ ranging from $0$ to $3.$ Let's see what happens within each of those loops:
$i=0$: then $j$ runs from $1$ to $3$ (three values), and so does $k.$ But there are only two values of $h$ ($2$ and $3$) for $k=1,$ one value of $h$ ($h=3$) when $k=2,$ and no values of $h$ at all (the loop never iterates even once) when $k=3,$ because $k+1=N.$ So adding up the numbers of $h$-loops for each $k,$ we get $2+1+0,$ and we get the same again for each value of $j,$ which makes $3\cdot(2+1+0)$ times through the innermost loop when $i=0.$
$i=1$: then $j$ and $k$ each take only two values ($2$ and $3$); $h$ takes only one value for $k=2$ and none for $k=3.$ Adding up all the innermost loop iterations, we have $1+0$ innermost iterations for each $j,$ for $2\cdot(1+0)$ innermost loop iterations altogether.
$i=2$: the only iterations of the middle two loops are for $j=3$ and $k=3,$ but when we get to the $h$ loop there are no values left to iterate over; the total is $1\cdot(0)$ iterations.
$i=3$: no iterations of any of the inner loops.
So adding up over all the times through the outermost loop, we get $3\cdot(2+1+0) + 2\cdot(1+0) + 1\cdot(0).$
What if $N=5?$ We then get more iterations of the inner loop while $i=0.$ If you follow the same reasoning as before, you get $4\cdot(3+2+1+0)$ iterations of the innermost loop, followed by $3\cdot(2+1+0)$ and so forth just like before; the total ends up at $4\cdot(3+2+1+0) + 3\cdot(2+1+0) + 2\cdot(1+0) + 1\cdot(0).$
See a pattern? (The reason I have not yet actually calculated the results of adding or multiplying any of these numbers is that I did not want to lose track of the pattern.) Once we see a pattern, if we can write the sum for any $N$ using a suitable notation, we can work with it algebraically. Extending the pattern to larger values of $N,$ the number of inner loops is
$$ f(N) = \sum_{m=1}^{N-1} \left( m \sum_{h=0}^{m-1} h \right). $$
Now the only thing left is to find a more convenient way to represent the total as a formula in terms of $N.$ We can use the fact that $\Sigma_{x=0}^{m-1} x = \frac{m(m-1)}{2}$ to reduce this sum of multiples of sums to just a sum of terms, each of which is a cubic polynomial. It will be useful to know the formulas for $\Sigma_{x=0}^m x^2$ and $\Sigma_{x=0}^m x^3$ too in order to solve this altogether. In the end, it shouldn't be too surprising if the leading term of the formula for the total number of loops is some constant times $N^4,$ since we do after all have four nested loops each counting up by $1,$ albeit from various starting values.
In case the example $N=4$ as described above is still not clear, here is a time sequence of all the values that the variables $i,$ $j,$ $k,$ and $h$ take on during all the loops for $N=4.$ $$\begin{eqnarray} \quad& i &\qquad & j \qquad & k \qquad & h \quad \\ \hline & 0 && 1 & 1 & 2 \\ & 0 && 1 & 1 & 3 \\ & 0 && 1 & 2 & 3 \\ & 0 && 1 & 3 & \\ & 0 && 2 & 1 & 2 \\ & 0 && 2 & 1 & 3 \\ & 0 && 2 & 2 & 3 \\ & 0 && 2 & 3 & \\ & 0 && 3 & 1 & 2 \\ & 0 && 3 & 1 & 3 \\ & 0 && 3 & 2 & 3 \\ & 0 && 3 & 3 & \\ & 1 && 2 & 2 & 3 \\ & 1 && 2 & 3 & \\ & 1 && 3 & 2 & 3 \\ & 1 && 3 & 3 & \\ & 2 && 3 & 3 & \\ & 3 && & & \\ \end{eqnarray}$$ Each line represents a new set of values that occurred. Blank entries mean there was no value of the variable that was less than $N$ when the variables to the left had the values shown. The inner loop executes only for lines where all the variables have values, which is just the lines where the entry for $h$ is not blank.
For example, consider the first four lines of the table. These show the iterations of the $k$ loop when $i=0$ and $j=1:$ two iterations for $k=1,$ then one for $k=2,$ and none at all for $k=3$ (indicated by the blank in the $h$ column), total $2 + 1 + 0.$ But these four lines occur almost exactly the same way three times; the only difference is the value of $j,$ which is $1,$ $2,$ or $3.$ These three repetitions of the pattern $2 + 1 + 0$ result in the term $3\cdot(2 + 1 + 0)$ to count the inner loop iterations for $i=0.$
Similar tables for $N=5$ or even $N=6$ are relatively easy to draw up if the pattern is not clear enough from this table.
One must make several assumptions to answer your question precisely. But making all the simplest assumptions, one has:
$k\ n \log{n} = 23$
and hence
$k \approx 3.3\ 10^{-3}$.
Then $k 10000 \log{10000} = 307$ second.
As for assumptions... note that a function that is in the class ${\cal O}(n^2)$ is also in ${\cal O}(n^3)$; conversely, some functions in ${\cal O}(n^3)$ are in ${\cal O}(n^2)$. For instance the function $g(n) = 1$ is in all of them! It is conceivable that your specific function is of constant time (which is in ${\cal O}(n\ \log{n}$)). So to answer your question you might assume that the bound is tight.
The proper way to pose such a problem would be to use the $\Theta (\cdot)$ notation, for asymptotically tight bound.
Best Answer
You can deduce an expression for $j$ at each iteration from its recursive formula.
To do that, notice that at the $l$-th iteration you just add $l$ in the previous value of $j$. Let $j_l$ be the value of $j$ in the the $l$-th iteration.
Then \begin{align} j_l&=j_{l-1} + l\\ j_1 &=1 \end{align}
It is clear now that \begin{equation} j_l = \sum_{i=1}^l i = \frac{l(l+1)}{2} \end{equation} where we used this to calculate the sum.
Now find the value of $l$ at which the inner loop will finish \begin{align} j_l > n\\ \frac{l(l+1)}{2} > n \end{align} Finally, we will overestimate $l$ to simplify the procedure. Notice that this overestimation makes no difference assymptotically.
\begin{align} l^2 &> 2n\\ l &> \sqrt{2n} \end{align}
So the overall complexity of this code is $\mathcal{O}(\sqrt{n}\log n)$.