- #1
lee534
- 7
- 0
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
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++ ;
none
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
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 < n3 ; j = 3*j )
sum++ ;
b.sum = 0 ;
for ( i = n ; i > 0; i = i/3 )
for ( j = 0 ; j < n3 ; 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<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: