time complexities of algorithms

user_16449380 0
Viewed 32

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

big-o algorithm
2 Answers

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)).

user_43677870

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
Admin1
Related