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

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

1 X N = 2

1 XX
2 X N = 3

2 XX
3 X N = 4

for i <--1 to n-1 do
for j <-- i+1 to n do

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.


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.