0

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

3
Contributors
3
Replies
4
Views
8 Years
Discussion Span
Last Post by sameeraict
0

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

0

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

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.