time complexity

Question

Find the time complexity of the following snippets

1.

for$\left ( i=1;i\leqslant n;i++ \right )$

      for$\left ( j=n/3;j\leqslant 2n;j=j+n/3 \right )$

                 $x=x+1;$

2.

for$\left ( i=1;i\leqslant n;i++ \right )$

      for$\left ( j=1;j\leqslant n;j=j+i \right )$

                 $x=x+1;$

Comments

7.$\Theta \left ( n \right ) and 8.\Theta \left ( nlogn \right )$?

---

i dont have any ans with me

---

Sol(7)-Inner loop runs costant time .So time complexity is equivalent to outer loop i.e.$\large \Theta (n)$.

Sol(8)-

$\large n+\frac{n}{2}+\frac{n}{3}+\frac{n}{4}+..........\frac{n}{n}$

$\large n\left (1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+..........\frac{1}{n} \right )$

$\large \Theta (nlogn)$

Answer 1

7.

for$\left ( i=1;i\leqslant n;i++ \right )$

      for$\left ( j=n/3;j\leqslant 2n;j=j+n/3 \right )$

                 $x=x+1;$

Time Complexity will be number of times   $x=x+1;$ will execute.

Inner Loop will execute exactly 6 times

$n/3\rightarrow 2n/3\rightarrow n\rightarrow 4n/3\rightarrow 5n/3\rightarrow 2n$ whatever the value of "n" is  and is Independent of outer loop

Thus time complexity will  number of times outer loop execute $\Rightarrow \Theta \left ( n \right )$

8.

for$\left ( i=1;i\leqslant n;i++ \right )$

      for$\left ( j=1;j\leqslant n;j=j+i \right )$

                 $x=x+1;$

time complexity = number of times "x=x+1" will execute .given below is the table$\Rightarrow$

i	j
1	n
2	n/2
3	n/3
4	n/4
$\cdots$	$\cdots$
n	n/n

time complexity $T\left ( n \right )=n+n/2+n/3+n/4+\cdots n/n$

$\Rightarrow T\left ( n \right )=n\left ( 1+1/2+2/3+n/4+\cdots 1/n \right )$

We know $\left ( 1+1/2+2/3+n/4+\cdots 1/n \right )\approx \log n$

$\Rightarrow T\left ( n \right )=\Theta \left ( n*logn \right )$

Comments

in short :

7. $n*\frac{2n}{n/3} = \Theta (n)$

8. $n*\sum_{k=1}^{n}\left ( \frac{n}{k} \right ) = \Theta (n\log n)$

http://stackoverflow.com/questions/25905118/finding-big-o-of-the-harmonic-series

---

yep :)

Answer 2

A. O(n)

Bcz inner loop always run for 6 times.

Bcz we start j=n/3 and every time increasing j by n/3  and want to reach upto 2n  i.e. 6(n/3)= 2n

So O(6n)=O(n)

B. O(nlogn)

Bcz our statement x=x+1 runs here

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

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

n(Harmonic Progression)

n(logn)

=O(nlogn)

Answer 3

It should be Option B for 7th

and Option D for 8th

Comments

explanation