0

I have the following code:

 sum = 0 ;
     i = n

 while( i ≥ 1){
     for ( j = 0 ; j < n^4 ; j++ ){
         sum++ ;
     }
     i = i/3 ;
 }

I have to find the time complexity in Θ notation in terms of n, and I'm not sure on how to approach this.

olearythe3rd
  • 1
  • 1
  • Perhaps here's a very informal way to get started. The code above has two main operations `sum++` and `i = i/3` (ignore all the looping stuff). Can you express the number of operations as a function of `n`? E.g. If you think `sum++` will execute `n` times and `i = i/3` will execute `5` times, then `f(n) = n + 5` would be your answer (that's not the answer though). Feel free to post when you think you found `f(n)`. Then we can move on to figuring out what Θ is. – user2570465 Jun 08 '17 at 19:57
  • Most of what's written in [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) can be applied here (yes, it's big-O and not big-Theta, but the approach would be similar, and big-O is often treated as meaning the same as big-Theta). Then there's also [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm). – Bernhard Barker Jun 08 '17 at 20:32

0 Answers0