0

I'm trying to practice algorithm complexities, How do I do this?! I don't understand the problem or what calculations I have to do to get it... ANY help would be wonderful!

int N = 50 ;
int sum = 0 ;
for (int n = N ; n > 0 ; n/=2 ) {
    for (int i = 0 ; i < n ; i++) {
        sum++ ;
    } 
}
OmG
  • 18,337
  • 10
  • 57
  • 90
StizzKizz
  • 17
  • 1

1 Answers1

1

You can write the number of iterations based on N for the inner loop in each iteration of the outer loop such as following:

T(N) = N + N/2 + N/4 + ... + 1 = N (1 + 1/2 + 1/4 + ...+ 1/(2^log(N)) = Theta(N)

So, the time complexity is in O(N) as well.

OmG
  • 18,337
  • 10
  • 57
  • 90