time and complexity

[xraaz]

how much time this algoritham takes in theta notation

a <---- 0
for i <------1 to n do
for J <........ 1 to i do
for k <-------j to n do
a = a+1

[Ramy Mahrous]

I think not less than 2N.
Right?

[darkagn]

a -> 1 step
For i = 1 to n -> takes n steps -> n+1 steps so far -> the 1 is negligible as n gets big so approx n steps so far
For j = 1 to i -> takes i steps for each n -> i*n so far -> approx n*n so far
For k = 1 to j -> takes j steps for each n*n -> j*n*n so far -> approx n*n*n so far
a = a+1 -> 1 step for each n*n*n -> 1*n*n*n

= n^3

[Ramy Mahrous]

yea darkgen, you're right I think your solution is eligable

[xraaz]

thanks for reply especially darkagn

[Rashakil Fol]

Should take something n^3 * log(n) given integers represented as products of primes.