1
$\begingroup$

An algorithm has a calculation whose worst case time complexity $T(x)=O(x^2)$ that outputs solutions $y$ & $z$ for input $x$ (the algorithm's worst case time complexity is greater than quadratic time):

for (i = 1; i <= x; i++)
    {
    for (j = 1; j <= i; j++)
        {
           // Some quadratic time calculation of x that gives y & z
        }
    }

A different algorithm using successive loops is created for a given $x$ that outputs the same $y$ & $z$:

for (i = 1; i <= x; i++)
    {
         // Some quadratic time calculation of x that gives y
    }
for (i = 1; i <= x; i++)
    {
         // Some quadratic time calculation of x that gives z
    }

Is the time complexity of the second algorithm $T_s(x)=O(x^2)$?

$\endgroup$
3
$\begingroup$

I think that the first algorithms running time is actually $\mathcal{O}(x^4)$.

  • The outer for loop executes exactly $x$ times,
  • the inner for loop executes at most $x$ times during every one of these $x$ iterations of the outer loop

In fact, the inner loop executes exactly $\frac{x(x+1)}{2}$ times, and $\frac{x(x+1)}{2} = \frac{x^2 + x}{2} = \mathcal{O}(x^2)$, since our asymptotic notation allows us to essentially ignore the constant factors.

So already we have a growing complexity of $\mathcal{O}(x^2)$. If we now consider the contents of the inner for loop, which you say is a quadratic time calculation of $x$. I read this as follows: the complexity of the inner loops body is a quadratic function of x $\rightarrow \mathcal{O}(x^2)$. My answer is based largely upon this assumption.

If my assumption is correct, then a time complexity of $\mathcal{O}(x^4)$ easily follows from this reasoning: the outer and inner for loop collectively produce $\mathcal{O}(x^2)$ iterations of some algorithm that takes $\mathcal{O}(x^2)$ steps to complete itself. An extremely informal (read: not quite right, but right enough to demonstrate a point) mathematical argument for this might be:

($x$ outer loop iterations) $\cdot$ ($x$ inner loop iterations) $\cdot$ ($x^2$ loop body steps) $= x^4$ total steps.

With the second algorithm, the same reasoning can be used. Again, we have some procedure, which takes $\mathcal{O}(x^2)$ steps to run, which is being executed $x$ times. This gives us $\mathcal{O}(x^3)$ steps in total. Since we have two loops of this form, we can conclude that algorithm 2 has a time complexity of:

$\mathcal{O}(x^3) + \mathcal{O}(x^3) = \mathcal{O}(x^3)$

Note that in this case we have two consecutive loops that, asymptotically speaking, do essentially the same amount of work. In reality it might be that our first loop which calculates $y$ performs some constant factor amount more or less steps than our second, which calculates $z$, but here that doesn't matter, since we're focusing on the rate of growth of our running time. One way of thinking about it is as follows:

$\mathcal{O}(x^3) + \mathcal{O}(x^3) = \mathcal{O}(x^3 + x^3) = \mathcal{O}(2 \cdot (x^3)) = \mathcal{O}(x^3)$.

Here we can drop the 2, since its a constant factor.

$\endgroup$
  • $\begingroup$ How do you get complexity of O(x^4) when the inner and outer loop both iterate at most x times, x * x = x^2, can you please note the book which shows that we should calculate time complexity on your way. $\endgroup$ – someone12321 Jul 25 '17 at 7:37
  • $\begingroup$ Did you read the answer? If something that takes $x^2$ steps at most to run is executed $x^2$ times, then it takes little thought to see tha t this algorithm can run at most $x^4$ times. $\endgroup$ – swingballchamp42 Jul 25 '17 at 11:26
  • $\begingroup$ Yes, that makes sense, i didn't understand you completely. $\endgroup$ – someone12321 Jul 25 '17 at 11:43
  • $\begingroup$ What I should have typed in my last comment was 'this algorithm can take at most $x^4$ steps to run'. Could you tell me which part of the answer was unclear so that I could change it please? $\endgroup$ – swingballchamp42 Jul 25 '17 at 11:45
  • $\begingroup$ @swingballchamp42 after learning more about time complexity (and yes, I have much yet to learn), I too get your final answer and am accepting it. Thanks! $\endgroup$ – Jeff Jul 25 '17 at 17:54
1
$\begingroup$

Algorithm 2 seems better in running time at first look, Provided that when your body inside loops takes same amount of time in iterations in both of the Algorithms. i.e. If I consider the asymptotic time as quadratic for the body of loop in each iteration for both algorithms, then Algorithm 1 will have O(x^4) time and Algorithm 2 will have O(x^3) time (As suggested in other answers given).

But what we see is not always exactly true. As there also exists 'Amortised Analysis' in the algorithms, which should be considered in the case, when the body inside the loops can take worst case time for few iterations and for other large part of iterations it takes totally different asymptotic time.

( If we have to consider the amortized analysis, then more information about the operations within the loop is needed to be sure. )

If more detailed information is needed on Amortised analysis, you can refer to "Chapter 17: Amortized Analysis" in "CLRS Introduction to Algorithms" book. It'll be an awesome read.

$\endgroup$
  • $\begingroup$ Freemn, wouldn't this be more a matter of efficiency than time complexity analysis? If the loop body is big oh of $n^2$, then [from a purely time complexity standpoint] does it really matter if the worst case scenario is grossly worse than the average time? $\endgroup$ – Jeff Jul 25 '17 at 17:59
  • $\begingroup$ In Amortized Analysis, we analyze a sequence of operations and guarantee a worst case average time which is lower than the worst case time of a particular expensive operation. $\endgroup$ – Freemn Jul 26 '17 at 6:48
  • $\begingroup$ Sample code: for(i=0; i<x; i++){ for (j=0; j<i; j++) {//'operation' }} Lets assume that the 'operation' inside for loop can take O(x^2) number of constant time operations in some of the iterations. But when you further analyze your problem, you may come to know that the total number of operations over all iterations of the loop can have at max O(x^3) constant time operations. Then in this case, amortised analysis will tell you that the overall complexity is not O(x^4), but only O(x^3). In many graph algorithms, these situations comes a lot. Hope this help. $\endgroup$ – Freemn Jul 26 '17 at 6:48
  • $\begingroup$ You can refer this link: geeksforgeeks.org/… for better understanding. $\endgroup$ – Freemn Jul 26 '17 at 10:41
  • $\begingroup$ I understand. That's cool. I was just making sure you weren't implying that occasionally $(O^3)$ could equal $(O^4)$ for really large $n$, as that would not be in line with big oh notation. Thanks! $\endgroup$ – Jeff Jul 26 '17 at 13:14
0
$\begingroup$

The time complexity of the second algorithm would be $T_s(x)=O(x)$. This is because the algorithm runs for a total of $2x$ times, which is $O(x)$.

The first algorithm would run $x$ times for its first run, $x-1$ for its second and so on so you get:

$\text{Algorithm 1} = 1 + 2 + ... + x-1 + x = O(n^2)$

The difference between the 2 algorithms is as such,

  • Algorithm 1: will run the outer loop $i$ times, and inner loop will run $i-j$ times. This is equivalent to $O(x^2)$, since $n ( n - y ) = n^2 - ny = O(n^2)$.

  • Algorithm 2: Will always run the first loop $x$ times, and the second loop $x$ times, giving $O(2x) = O(x)$.

Although your complexity time is correct due to the definition of $O$, since Algorithm 2 is $g(n)= O(n) \leq O(n^2)$, and so $g(n) =O(n^2) $.

This has to do with the actual definition of O-notation. Take a look at this link for more information.

Edited to reflect quadratic function in body loop:

Where the quadratic is taking some time (the exponent can be 2 for quadratic, or for any number x >= 1)

$\text{Work required} = O(n^x)$

$\text{Algorithm 1(without taking quadratic into account)} = O(n^2)$

$\text{Algorithm 1 complete} = n^x * n^2 = n^{x+2} = O(n^{x+2})$

For algorithm 2, we can assume

$\text{Algorithm 2} = n^x * n + n^x * n = n^{x+1} + n^{x+1} = 2n^{x+1} = O(n^{x+1})$

So in your example $\text{x = 2}$, so it would actually be $O(n^3)$ and not $O(n^2)$

$\endgroup$
  • 2
    $\begingroup$ The comment in the loops could be interpreted to mean that the loop body already takes quadratic time. $\endgroup$ – adrianN Jul 20 '17 at 9:32
  • $\begingroup$ @SDhaliwal, adrianN is correct, the comment in the loops does mean that the loop body already takes quadratic time. Also, because of the nested loop of the first, it should have a longer running time than the inner loop running time. Could you check your math again? Thanks. $\endgroup$ – Jeff Jul 20 '17 at 11:20
  • $\begingroup$ @SDhaliwal , could you edit your answer to reflect that the loop body takes quadratic time? And I'll accept it. Thanks. $\endgroup$ – Jeff Jul 23 '17 at 21:37
  • $\begingroup$ @Jeff I've edited my answer let me know if anything is unclear, or you can see any mistakes(sorry for the late reply was on vacation) $\endgroup$ – SDhaliwal Jul 25 '17 at 0:10
  • $\begingroup$ @SDhaliwal, no problem. Hope you had a good vacation. Going over it now. $\endgroup$ – Jeff Jul 25 '17 at 17:29

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.