# Time complexity(Big oh)

1. Mar 5, 2014

### lee534

Hi this is my first post and I having an extremely hard time finding time complexity in code
note: I have had no compsci experience (since it was career change) and the professor only went over this for 30 mins
1. The problem statement, all variables and given/known data
What is the time complexity (in Θ –notation) in terms of n ? (the red is what is throwing me off)
a.sum = 0 ;
for ( i = 0 ; i < n ; i++ )
for ( j = 1 ; j < n3 ; j = 3*j )
sum++ ;
b.sum = 0 ;
for ( i = n ; i > 0; i = i/3 )
for ( j = 0 ; j < n3 ; j++ )
sum++ ;
2. Relevant equations
none

3. The attempt at a solution
a.
assignments: sum = 0, i = 0, j = 1, j=3*j : (1+1+3*n)
conditions: j<n3, i<n: 3*(n+1+n(n3+1)
increments:i++,sum++; n+n3
O(n4)

b.(this one I'm taking a big educated guess)
assignments: sum = 0, i = n, i = i/3, j=0: 1+1+n+n/3
conditions: j<n3, i>0: n/3+1+n(n3+1)
increments:j++,sum++; n*n3+n*n3
O(n4)

and if you can explain to me as if I'm a child that would be great!
Thank you

Last edited: Mar 5, 2014
2. Mar 5, 2014

### jackarms

Careful, the loops for (a) are misleading. You have the right idea for the outside loop -- it'll all just be n. But for the inside, essentially what you do is multiply whatever time complexity you have for the inner loop by the complexity of the outer loop (it looks like you were adding them). An easier case for this is two for loops that are both $O(n)$. The inner loop goes for $O(n)$ $n$ times, so that becomes $n \cdot O(n)$, or $O(n^{2})$.

Also for (a), consider what happens when j goes up to n3, but each iteration you multiply j by three. How do you think these effects will compare? Try writing out a list of values j will take on.

For (b), the code in red can be difficult to analyze. If it were instead multiplying by 3 each time, this would be exponential, right? So if you're dividing, then what's the opposite of an exponential function?

3. Mar 6, 2014

### lee534

So is it easier to analyze it by loops? Because I found this method online and the professor did not teach how us to read code as you are describing (he was also using a different format from this problem, but I'm guessing it's analyzed the same?).

okay so for a. can we look at it this way?
a.
assignments: sum = 0, i = 0, j = 1, j=3*j : (1+1+3*n) → O(n)
conditions: j<n3, i<n: n+(n)(3n)3 → O(n4)
increments:i++,sum++; n+n(n3)
O(n4)

or

a.sum = 0 ;
for ( i = 0 ; i < n ; i++ ) → O(n)
for ( j = 1 ; j < n3 ; j = 3*j ) →n(3n)3→O(n4)
sum++ ;
O(n) + O(n4) → O(n4)

b.
b.sum = 0 ;
for ( i = n ; i > 0; i = i/3 ) → 3√n → O(n1/3)
for ( j = 0 ; j < n3 ; j++ ) → (n1/3)*(n3) → n
sum++ ;
O(n)

thank you for helping me understand

Last edited: Mar 6, 2014