# What is the time complexity (in big O notation) given the following code?

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++ ;

• 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)$ – user40276 Nov 26 '13 at 2:47

## 1 Answer

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