ProgrammingComplexity Analysis (Big 0 notation)
Posted:

ProgrammingComplexity Analysis (Big 0 notation)Posted:

Frostd
  • WIP 5.1
Status: Offline
Joined: Jul 15, 20168Year Member
Posts: 795
Reputation Power: 118
Status: Offline
Joined: Jul 15, 20168Year Member
Posts: 795
Reputation Power: 118
Anyone know how to work out complexity analysis and want to help? Struggling badly

Its for C++ code.

bool bInsert(int*& pi, int& size, int pos, int val)
{
if (pos < 0 || pos > size) {
cout << "pos is out of range" << endl;
return false;
}
// new array size after insertion
size++;
// new array
int* piNew = new int[size];
if (piNew == NULL)
return false;
// copt pi to piNew & insert val
for (int i = 0; i < pos; i++)
piNew[i] = pi[i];
piNew[pos] = val;
for (int i = pos + 1; i < size; i++)
piNew[i] = pi[i - 1];
// delete old array
delete[] pi;
// point pi to the new array
pi = piNew;
return true;
}
#2. Posted:
CriticaI
  • Christmas!
Status: Offline
Joined: Nov 05, 201311Year Member
Posts: 2,749
Reputation Power: 452
Status: Offline
Joined: Nov 05, 201311Year Member
Posts: 2,749
Reputation Power: 452
I completely misread your question the first time.

You're looking for Big O notation.

For loops are O(n) aka linear time. Essentially, the more data you have the longer it will take at a proportional rate. For example, if it takes 3 seconds for 3 items, it would take 500 seconds for 500 items.

Your algorithm is O(2n) because you are doing a linear search for the position 2 times.

If you are working with large arrays you will want to use a binary search instead because binary search is O(log n) which is significantly more performant in the long run.

Here is a video to get you started.
Users browsing this topic: None
Jump to:


RECENT POSTS

HOT TOPICS