hi, i need some help on analysing the complexity of above algorithm,

for i <--1 to n-1 do

for j <-- i+1 to n do

statement of O(1) time

end of the loops.

please give me ur's ideas

sameeraict 3 Newbie Poster

hi, i need some help on analysing the complexity of above algorithm,

for i <--1 to n-1 do

for j <-- i+1 to n do

statement of O(1) time

end of the loops.

please give me ur's ideas

wildgoose 420 Practically a Posting Shark

Your problem is pretty simple! Think of it as a kind of two dimensional array. You can solve it by calculation but visualy.

<i>

--- N = 1

1 X N = 2

1 XX

2 X N = 3

1 XXX

2 XX

3 X N = 4

for i <--1 to n-1 do

for j <-- i+1 to n do

mytime19 0 Junior Poster in Training

for i <--1 to n-1 do --------------> complexity is o(n) time

for j <-- i+1 to n do --------------> if it is nested then it would be previous complexity(new complexity) ==>> (O(n)(O(n)))==> O(n square)

if both the loops were separate and they were not nested one's then complexity of loop1 ==> O(n) and loop2 ==> O(n) add complexity of all the statements ==> O(n) + O(n) ==> O(n) and if there isn't any loop in any statement say it's like if condtn ==> O(1) and then the total complexity would be O(n) + O(n) + O(1) ==> O(n).

Hope this would make you complexity thingy clear.

Cheers,

Lucky

sameeraict 3 Newbie Poster

thanks so for your detailed description. i got ur points .

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.