edited by
24,331 views
50 votes
50 votes

Consider the following C function

int 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 $\Theta$ notation is

  1. $\Theta(n \sqrt{n})$
  2. $\Theta(n^2)$
  3. $\Theta(n \: \log n)$
  4. $\Theta(n^2 \log n)$
edited by

7 Answers

Best answer
54 votes
54 votes
Inner for loop is dependent on $i$, so for each $i$ we have to check no of times inner loop operating..

It ll be something like

 $\frac{n-1}{1}+\frac{n-1}{2}+\frac{n-1}{3}+...........+\frac{n-1}{n-1}+1$

$\frac{n}{1}+\frac{n}{2}+\frac{n}{3}+......+\frac{n}{n-1}-\log(n-1)$

$n\{{\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+.....+\frac{1}{n-1}}\} - \log(n-1)$

$n\log(n-1)-\log(n-1)$

$n\log(n-1)$

$n\log n$

Correct Answer: $C$
edited by
112 votes
112 votes

$i=1 \rightarrow j : 1 ..2..3..4..5..6..7..8..9..10......approx (n times)$

$i=2 \rightarrow j : 1 ..3..5..7..9..11..13.................approx (n/2 times)$

$i=3 \rightarrow j : 1 ..4..7..10..13..14..17..............approx (n/3 times)$

$T(n)= n + n/2 + (n/3) + (n/4)+ (n/5) + (n/6)......... =\Theta (nlogn)$ {best option}

12 votes
12 votes

Ans) c

First time inner loop run -----n times

2nd   time    ''           ''      ''----n/2 times

Then,n/3,n/4....till  n/n=1 time

Total=n+n/2+n/3+n/4+n/5+......+n/n=n(1+1/2+1/3+...+1/n)=⊝(nlogn) (approx)

7 votes
7 votes
for i=1;j will run=1to n=n tym

​​​​​​i=2;j will run =1ton=n/2 tyms

i=3;j will run 1to n=n/3 tyms

i=4;j will run 1 to n=n/4 tyms

...so on i=n; j will run 1to n=1 tym;

therefore j will run in total=(n+n/2+n/3+n/4+..........1)=n(1+1/2+1/3+1/4.......)=nθ(log n)=θ(nlogn)

option c
Answer:

Related questions

25 votes
25 votes
7 answers
1
khushtak asked Feb 14, 2017
6,788 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$...
47 votes
47 votes
6 answers
2
Madhav asked Feb 14, 2017
17,766 views
Consider the recurrence function$$T(n) = \begin{cases} 2T(\sqrt{n})+1, & n>2 \\ 2, & 0 < n \leq 2 \end{cases}$$Then $T(n)$ in terms of $\Theta$ notation is$\Theta(\log \l...
41 votes
41 votes
4 answers
3
Arjun asked Feb 14, 2017
20,969 views
A message is made up entirely of characters from the set $X=\{P, Q, R, S, T\}$. The table of probabilities for each of the characters is shown below:$$\begin{array}{|c|c|...
29 votes
29 votes
5 answers
4
Madhav asked Feb 14, 2017
7,929 views
The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the ...