edited by
475 views
0 votes
0 votes
I couldnt attempt during the exam :(

for( int i=0; i<n; ++i )

{

    for( int j=0; j<n; j+= i )

    {

        (some statements I dont remember)

    }

}

Time complexity of the above code is:

Options:

A) $\theta(n$\sqrt{n}$)$

B) $\theta(n2)$

C) $theta(n.logn)$

D) $theta(n2.logn)$
edited by

3 Answers

1 votes
1 votes

The sequence would be:

n + n/2 + n/3 + n/4 + n/5 + ...+ n/n

= n . [1 + 1/2 + 1/3 + 1/4 + ...+ 1/n ]

Lets denote the summation part as S.

So, S

= 1 + 1/2 + 1/3 + 1/4 + ...+ 1/n

= 1 + (1/2 + 1/3) + (1/4 + 1/5 + 1/6 + 1/7) + (1/8 + 1/9 + ...+ 1/15) + ...+ ( 1/(n/2) + ... + n)

= 1 + (1/2 + 1/2) + (1/4+ 1/4+ 1/4 + 1/4) + (1/8 + 1/8 + ...+ 1/8) + ...+ ( 1/(n/2) + ... + 1/(n/2) )

Now, let x=1/2

So, S

= 1+ (2x) + (4x2) + (8x3) + ...+ (n/2).(x)log(n/2)

= (2x)0 + (2x)1 + (2x)2 + ... + (2x)log(n/2)

Now, 2x = 2 * (1/2) = 1

$\therefore$ S = 1 + 1 + 1 + ...( log(n/2) times ) = logn

Hence, T(n) = $\theta(n.logn)$

0 votes
0 votes
n + n/2 + n/3 + n/4 +.............+1

n (1+1/2+1/3+1/4+.............)

Now 1+1/2+1/3+........+1/n is nothing but H.P SERIES (harmonic progression) and sum of H.P till n terms is logn.

Therefore n.logn = theta (nlogn )

Related questions

50 votes
50 votes
7 answers
2
Madhav asked Feb 14, 2017
24,349 views
Consider the following C functionint fun(int n) { int i, j; for(i=1; i<=n; i++) { for (j=1; j<n; j+=i) { printf("%d %d", i, j); } } }Time complexity of $fun$ in terms of ...
25 votes
25 votes
7 answers
3
khushtak asked Feb 14, 2017
6,794 views
Match the algorithms with their time complexities:$$\begin{array}{|l|l|}\hline \textbf{Algorithms} & \textbf{Time Complexity} \\\hline \text{P. Tower of Hanoi with $n$...
0 votes
0 votes
1 answer
4
admin asked Apr 1, 2020
914 views
An algorithm is made up pf two modules $M1$ and $M2.$ If order of $M1$ is $f(n)$ and $M2$ is $g(n)$ then the order of algorithm is$max(f(n),g(n))$$min(f(n),g(n))$$f(n) + ...