What are the time complexities of these two algorithms? I got 3n/2 6 for the first one, and 3logn 6 for the second and I'm not sure if I'm doing them right.

int i  = 0 ;
double evenSum = 0.0 ;
while ( i < n) {
    evenSum = evenSum   data[i] ;
    i  = 2;
}
StdOut.println(evenSum);

and the second is similar it just multiples by 2

int i = 0 ;
double evenSum = 0.0 ;
while ( i < n) {
    evenSum = evenSum   data[i] ;
    i *= 2;
}
StdOut.println(evenSum);

and I got 3n/2 6 and 3log n 6

CodePudding user response：

Time complexity for the first one is O(n). The second one is infinite loop. for (i = 0) * 2 => 0 and won't exit loop. In case i = 1, then its time complexity is O(log(n)).

CodePudding user response：

Note that for the second code, your loop will never close as i is initialized to 0, which means i=i*2 will be 0 each time.

Time complexity is different from the number of steps taken to execute.

• If you are asking about time complexity then for the first it will be O(N) as it has linear iteration i.e. i=i 2
• For the second code, assuming that you plan to correct the initialization of i it will be O(log(N)) as it has exponential iteration i.e i=i*2