edited by
2,083 views

3 Answers

Best answer
4 votes
4 votes

the inner loop is additive increase this makes growth as $\mathcal{O}(n)$

the outer loop is multiplicative decrease, this makes shrinkage as $\mathcal{O}(\log_2 (n) )$

both are in serial connection, therefore $\text{Time Complexity} = \mathcal{O}\left( n\log_2(n) \right)$

answer = option B


the recurrence relation that governs the value of $j$ is given as:
$$\begin{align*} j_m &= j_{m-1} + m \\ a_n &= a_{n-1} + n \qquad \text{; rewriting the relation} \end{align*}$$

such a recurrence relation is non-homogeneous recurrence relation.
whose solution is in the form $$\begin{align*} a_n &= a_n^p + a_n^h\\ &= \text{Particular Solution} + \text{Homogeneous Solution} \end{align*}$$ 

for homogeneous solution we can see it directly as $r=1$ so $a_n^h = c_h$ where $c_h$ is a constant.
the $F(n)$ here is a linear function whose trial solution will be in the form $d_0+d_1 n$

combining which gives us that the inner loop is $\mathcal{O}(n)$

edited by
2 votes
2 votes
In inner loop j=1 for 1st iteration

                     j=1+2 for 2nd iteration.

so on            j=1+2+3+4+......+k for kth iteration.

ie k(k+1)/2=n    =>     k=O(sqrt(n)).

outerloop runs for O(logn).Total time complexity is O(logn.sqrt(n)).Answer should be option D???.If wrong plss correct me.

Related questions

1 votes
1 votes
1 answer
1
shikharV asked Nov 15, 2015
1,029 views
The answer to the above problem is A but I am expecting it to be D as constant amount of work is required to solve each subproblem.
1 votes
1 votes
0 answers
3
kartikeya2812 asked Jun 16, 2018
394 views
What will be the time complexity of the following algorithm ?A(n){if(n<=1) return 1;for(i=1;i<n;i++){ for(j=0;j<3;j++){ A(n-1) } }}
7 votes
7 votes
3 answers
4
bts asked May 29, 2018
1,870 views
Why is recursive equation of following code $T(n)=T(n/2)+O(1)$, not $T(n)=8*T(n/2)+O(1)$? int x=0; int A(n) { if(n==1) return 1; else { X+=8A(n/2)+n^3; } return X; }