complecsity of an algorithm

[sameeraict]

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]

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]

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]

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