Basic Complexity Analysis

Given two arrays \(A\) and \(B\), both of size \(n \geq 1\), which of these three algorithms runs the slowest?

1
2
3
4
5
Algorithm algo1(A,B)
   b ← A[0]
   for i ← 1 to n -1 do
      b ←  b + A[i]
   return b
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
Algorithm  algo2(A,B)
   c ←  0
   for i ←  1 to n -1 do
     s ←  0
     for j ←  1 to n -1 do
        s ←  s + A[0]
        for k ←  1 to n -1  do
           if k % 1 = 0 then
              return s                     
           s ←  s + 9

   return c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
Algorithm  algo3(A,B)
   c ←  0
   for i ←  1 to n -1 do
     s ←  0
     for j ←  1 to n -1 do
        s ←  s + A[0]
        for k ←  1 to j do
           s ←  s + A[k]
        if B[i] = s then
           c ←  c + 1
   return c
×

Problem Loading...

Note Loading...

Set Loading...