Running time of algorithm (effect of j*j in for loops) - Theta Runtime

Question

In Theta notation what are the running times of these algorithms?

Algorithm 1

for i=1..n
 j=1
 while j*j <= i:
 j = j + 1

Since the outer loop is going to n and the inner loop is going to sqrt(n). My guess is that it is Θ(n^2)

$$ \sum_{i=1}^{n} O(1) \sum_{j=1}^{\sqrt n}O(1) = \sum_{i=1}^{n} \sqrt j*\sqrt j = \theta(n^2) $$

Thought process for the summations: number of terms * max term

Algorithm 2.

for i=1..n
 j=2
 while j <= i 
 j = j * j

j performs similar to a log function. Since the outer loop is n. My guess is $Θ(n\log n)$

$$ \sum_{i=1}^{n} O(1) \sum_{j=2}^{\log n}O(1) = \sum_{i=1}^{n} (\log n -2) * O(1) = \theta (n * (\log n -2)) = \theta (n\log n) $$

Answer 1

1

For the first case, you had the right idea, but just had some algebra mistakes.

for i=1..n
 j=1
 while j*j <= i:
 j = j + 1

Let $T(n)$ be the time complexity. $$T(n) = \sum_{i=1}^n\sum_{j=1}^\sqrt{i}1\leq \sum_{i=1}^n\sqrt{n}=\leq n^{3/2}$$ $$= O(n^{3/2})$$

2

I'm assuming you meant the pseudocode below since it is more analogous to your first case (I believe the pseudocode you posted has the same complexity). You are correct though, it is $O(n\log n)$ for the reason you described.

for i=1..n
 j=2
 while j <= i
 j = j * j

• Thoma Bonparte: Firstly, I just want to say thanks! Secondly, I did mean the one I had up there for 2 :)
• oerpli: Firstly, you seem to have an syntax error up there (for 1=1..n should likely be for i=1..n)! Secondly (if my assumption with i=... is correct), his answer is still correct (it doesn't make a difference in O/Theta notation, whether j is bounded by i or n).
• Throckmorton: @oerpli yes that is what I meant when I said his original pseudocode would have the same complexity :p
• Thoma Bonparte: @BryceKile can'y you make a case for $\theta (n \log \log n) $ for the algorithm you proposed for Algorithm 2???
• Throckmorton: @ThomaBonparte stackoverflow.com/questions/21152609/…