0
$\begingroup$

Before asking the question I read through my textbook and the wikipedia page for big O notation and I am still having a hard time understanding how to calculate time complexity in big O notation.

How would I go about calculating the time complexity of the following code?

sum = 0 ;

for ( i = 0 ; i < n ; i++ )

       for ( j = 1 ; j < n3 ; j = 3*j )

        sum++ ;
$\endgroup$
  • 2
    $\begingroup$ you have two loops and at each time you pass through a loop you spend a constant time, hence it's $T(n) \leq k n \frac{n}{3} = O(n^2)$ $\endgroup$ – user40276 Nov 26 '13 at 2:47
1
$\begingroup$

It depends on your undefined variable n3:

  • If this means $3n$ or even $n^3$ the inner loop runs in $\log(n)$ time because it computes the exponential function $3^j.\;$ Therefore the overall complexity will be $O(n\log n)$.

  • If n3 means $3^n$ the count for the inner loop is $\approx n$ and and you have $O(n^2)$-

$\endgroup$

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.