447 views

2 Answers

Best answer
3 votes
3 votes

Lets count the number of iterations which gives us the time complexity :

When i = 1 , m  =  floor(n/1) = n

when  i  =  2  ,   m  =  floor(n/2) which can be written as n/2 for complexity calculation convenience

when  i  =  3 ,   m  =  floor(n/3) which we write n/3 

..... and so on till  

i  =  n   ,   m  =   floor(n/n)  = 1

So no of times the program runs..For that we consider no of times the inner loop is run which is defined by the value of m for each iteration.

Hence time complexity   =   n[ 1 + 1/2  + 1/3 .........+ 1/n]

                                    =    θ(nlogn)   [ Since 1 + 1/2 +.........1/n =  logn ]

Hence A) option is true

selected by
1 votes
1 votes
when i = 1 inner loop executes n/1 times, i = 2 inner loop executes n/2,... i= n inner loop executes n/n times
So number of times count = count+1 is executed is n/1 + n/2 + ... + n/n = n (1+1/2+...+1/n)  .
1+1/2+..+1/n is harmonic series and it can be shown that 1+1/2+1/3+...+1/n = Theta(lg n)
So ans is theta(nlgn) Option (a)

http://math.stackexchange.com/questions/1605108/show-that-the-harmonic-series-is-theta-log-n
http://stackoverflow.com/questions/25905118/finding-big-o-of-the-harmonic-series

Related questions

0 votes
0 votes
0 answers
2
0 votes
0 votes
1 answer
3
NeelParekh asked Jul 27, 2023
264 views
If an array is split in the form of increasing and decreasing order then what is TC to find minimum element in the array?
2 votes
2 votes
1 answer
4
h4kr asked Dec 30, 2022
437 views
What is the correct time complexity in $\theta()$ ?