1
$\begingroup$

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) $$

$\endgroup$
1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Firstly, I just want to say thanks! Secondly, I did mean the one I had up there for 2 :) $\endgroup$ – Thoma Bonparte Sep 25 at 11:50
  • $\begingroup$ 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). $\endgroup$ – oerpli Sep 25 at 13:36
  • $\begingroup$ @oerpli yes that is what I meant when I said his original pseudocode would have the same complexity :p $\endgroup$ – Bryce Kille Sep 25 at 13:38
  • $\begingroup$ @BryceKile can'y you make a case for $\theta (n \log \log n) $ for the algorithm you proposed for Algorithm 2??? $\endgroup$ – Thoma Bonparte Sep 26 at 10:59
  • $\begingroup$ @ThomaBonparte stackoverflow.com/questions/21152609/… $\endgroup$ – Bryce Kille Sep 26 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.