# What is the Big-O time complexity of this algorithm [closed]

I was wondering what the run time of this small program would be?

``````#include <stdio.h>

int main(int argc, char* argv[]) {

int i;
int j;
int inputSize;
int sum = 0;

if(argc == 1)
inputSize = 16;
else
inputSize = atoi(argv[i]);

for(i = 1; i <= inputSize; i++){
for(j = i; j < inputSize; j *=2 ){
printf("The value of sum is %d\n",++sum);
}
}
}
``````

n

``````Σ floor(log n - log (n-i)) = ?
``````

i =1

and that each summation would be the floor value between `log(n) - log(n-i)`.

Would the run time be `n log n`?

-
Sounds like you're asking for the Big-O complexity of the program. We have no idea what the run time is -- that'll depend on all sorts of things such as the hardware you're running on, what other processes are running at the same time, etc. –  Caleb Oct 19 '12 at 17:05
Seems like a homework problem to me. –  Scott Whitlock Oct 19 '12 at 17:08
Yeah I am asking about the Big-O complexity. I am not very good at it and would like to better at it. –  grebwerd Oct 19 '12 at 17:40
The outer loop is clearly `O(inputSize) ~ O(n)`. And because `j` doubles at each iteration the inner loop is `O(log(inputSize - i)) ~ O(log n)`. So yes, the overall bound would be `O(n)O(log n) ~ O(n log n)`.