MIT ASSIGNMENT

Question

FIND THE TIME COMPLEXITY

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

Comments

IS IT O(nlogn)

---

LETS SEE LOOP

 

FOR  i=1 IT RUNS   LOG(N LOGN)

FOR I=2 IT RUNS LOG (N LOGN -1)

.......................................... FOR I =N IT RUNS LOG (NLOGN-N)

SO TOTAL TIMES IT RUN IS LOG (N LOGN) +LOG( N LOGN -1) .........................+LOG(N LOGN-N)
 

 

 

.

.

---

LOG A+LOG B IS NOT LOG(A+B)

YOU CANNOT TAKE LOG COMMON LIKE THIS

---

SO TOTAL TIMES IT RUN IS LOG (N LOGN) +LOG( N LOGN -1) .........................+LOG(N LOGN - N)

IT SHOULD BE THEN-

LOG( NLOGN*(NLOGN-1)*(NLOGN-2)...........*(NLOGN-N))

TAKING ASYMPTOTICALLY LARGEST TERM WE WILL GET-

= LOG( (NLOGN)^N)

=LOG(NLOGN)*N

=O(NLOGN)

---

HOW DID U MULTIPLY NOT GETTING THAT ?

---

LOG A+LOG B=LOG(A*B)

JUST USE THIS.

---

WHY ARE YOU WRITING

N * LOG(NLOGN) AS O(NLOGN)

AS N *LOG(N LOGN)  >= N*LOGN

---

i think its same

nlogn or n*logn

---

sushmita  i am writing about 

n log(nlogn) and nlogn AND  BOTH OF THEM ARE DIFFERENT

---

n log(nlogn) and nlogn AND  BOTH OF THEM ARE DIFFERENT

log(nlogn)=logn+log(logn)

hence n log(nlogn)=n*( logn+log(logn))

taking asymptottically largest value

it is O(n ogn)

Is it clear now?

---

THANKU :)

---

Answer is nlog(nlogn) i am sure

---

How come first loop runs LOG(N LOGN) times?

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

Answer 1

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

Answer 2

The answer comes out to be O(n³ logn)