Question

Big Oh notation...

int sum = 0
for(int i = 1; i < N; i *=2)
for(int j = 0; j < N; j++)
sum++;

the outer loop runs Log n times right?
and the inner loop runs [1+2+4+8...] times so N? right

what would the total big Oh of the algorithm be? and why?

Answer 1

This big O of an a composition of two functions is the product of the big O of the respective functions.