retagged by
797 views
0 votes
0 votes

FIND THE TIME COMPLEXITY

int i=1,j;
for(;i <= n;i + +)
{
    for(j = i; j <= nlogn; j∗= 2)
    {
        sum++; 
    }
}
retagged by

2 Answers

2 votes
2 votes
1. first for loop runs n times

2. second for loop runs log(nlogn) :

 since j = 1, 2, 4, 8, 16,........nlogn.......2^n but it runs only till nlogn

assume some 2^k = nlogn

solving we get k as log(nlogn)

By product rule: T(n) =  n*log(nlogn)

n*Log(nlogn) = n[log(n) + log(logn) ] = nlog(n) + nlog(logn)

By taking Big O , nlogn > nlog(logn)

hence the answer will be nlogn
edited by

Related questions

0 votes
0 votes
1 answer
1
sushmita asked Sep 28, 2018
847 views
Find the complexity of the following code fragment:int i = 1; for(; i <= n logn; i++) { for(i++; i <= n; i++) { printf("1") } }
1 votes
1 votes
2 answers
2
sushmita asked Sep 28, 2018
708 views
Find the complexity of the following function when called with some integer n:void foo(n) { int i,j,k,x=0; for (i=1 ; i <= n ; i++) for (j=1 ; j <= i * i ; j++) for ( k ...
1 votes
1 votes
1 answer
3
Shubhanshu asked May 9, 2017
628 views
How the worst case of merge sort is O(n^2) according to the given MIT assignment pdf:-explain ?
2 votes
2 votes
3 answers
4
sushmita asked Mar 21, 2017
7,031 views
For each group of functions, sort the functions in increasing order of asymptotic (big-O) complexity:$\begin{align*} &(a) \;\;f1(n) = n^{0.999999} * \log n \\ &(b) \;\;f2...