Understanding Time Complexity in Code: Explained for Beginners"

[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

Homework Statement

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 < n³ ; j = 3*j )
sum++ ;
b.sum = 0 ;
for ( i = n ; i > 0; i = i/3 )
for ( j = 0 ; j < n³ ; j++ )
sum++ ;

Homework Equations

none

The Attempt at a Solution

a.
assignments: sum = 0, i = 0, j = 1, j=3*j : (1+1+3*n)
conditions: j<n³, i<n: 3*(n+1+n(n³+1)
increments:i++,sum++; n+n³
O(n⁴)

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<n³, i>0: n/3+1+n(n³+1)
increments:j++,sum++; n*n³+n*n³
O(n⁴)

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

 

[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 n³, 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?

 

[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<n³, i<n: n+(n)(3n)³ → O(n⁴)
increments:i++,sum++; n+n(n³)
O(n⁴)

or

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

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

thank you for helping me understand