CODEWITHSUNDEEP
algorithmdata-structuresbig-otime-complexity
Richard
Richard

Reputation: 6116

BigO time complexity of algorithm

What is the bigO time of this algorithm? Input: Arrays A and B each sorting n>=1 integers Output: The number of elements in B equals to the sum of prefix sums in A

c=0
for i=0 to n-1 {
  s=0
  for j=0 to n-1 {
    s=s+A[0]
    for k=1 to j {
      s=s+A[k]
    }
  }
  if B[i]=s {
    c=c+1
  }
}
return c

I got n(n+2)(n+2)+1 which is n^3+4n^2+4n+1 which is O(n^3)

Upvotes: 1

Views: 936

Answers (2)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

To determine the order of growth, formally, you may proceed like the following:

enter image description here

Upvotes: 1

noMAD
noMAD

Reputation: 7844

If you are just looking for the BigO here, all you have to do is to find out the number of loops how many of them are nested. In your case you have two loops (nested) hence it would be O(n * n) = O(n^2)

P.S Even though your inner loop does not go as many times as the outer one the BigO still remains the same.

Upvotes: 1

Related Questions