CODEWITHSUNDEEP
c++algorithmtime-complexityasymptotic-complexity
Ami
Ami

Reputation: 195

Complexity of algorithm including dynamically allocated array

I wrote a program that gets from user-interface an array of numbers (natural numbers) and injects them into a dynamically allocated array. I'm getting stuck with calculating the big-O of the program and would appreciate your help with how to evaluate that. my guess is O(nlogn) but I don't know how to prove\show it.

The code:

int* gradesToArr(int& arr_size, int& numOfGrades)   //function that gets parameters of initial array size (array for array of numbers received from user), and actual amount of numbers that been received.
{
    int input, counter = 0;
    arr_size = 2;
    int* arr = new int[arr_size];                   //memory allocation for initial array for the sake of interface input.


    do {                                            //loop for getting and injecting numbers from the user interface right into the Array arr.
        if (counter < arr_size)
        {
            cin >> input;
            if (input != -1)
            {
                arr[counter] = input;
                counter++;
            }
        }
        else
            arr = allocateArr(arr, arr_size);       //in case of out-of-memory, calling the function "allocateArr" that allocates twice larger memory for arr.
    } while (input != -1);

    numOfGrades = counter;                          //update the size of numOfGrades that indicates the amount of grades received from user and inserted to the array.
    return arr;
}

int* allocateArr(int Arr[], int &size)              //function that allocates bigger array in case of out-of-memory for current quantity of elements.
{
    int* fin;

    fin = new int[size * 2];                        //allocates twice more space then been before
    for (int i = 0; i < size; i++)                  //copies the previous smaller array to the new bigger array
        fin[i] = Arr[i];                            

    delete[]Arr;                                    //freeing memory of Arr because of no need, because the data from Arr moved to fin.
    size *= 2;
    return fin;
}

Upvotes: 2

Views: 787

Answers (1)

Ralph Tandetzky
Ralph Tandetzky

Reputation: 23600

The total complexity is O(n). You'll get O(log(n)) memory allocations and you might think, you get O(n) operations per memory allocation. But that is not true, since the number of operations you do is much smaller in the in the first iterations. Most of the work is the copying. The last time you copy, you have less than n copy operations. The time before you have less than n/2 copy operations. The time before you have n/4 copy operations and so on. This sums up to 

n + n/2 + n/4 + ... + 2 < 2*n

copies of individual array elements. Therefore, you have 

O(2*n) = O(n)

operations in total.

Simplifying code

You basically implemented the memory management of an std::vector manually. This makes your code unnecessarily complicated. Just use std::vector instead and you'll get the same performance, but less risk of messing things up. Like so:

#include <vector>
#include <iostream>

// reads grades from standard input until -1 is given and 
// returns the read numbers (without the -1). 
std::vector<int> gradesToArr()
{
    std::vector<int> result;    
    for(;;) 
    {
        int input = 0;
        std::cin >> input;
        if ( input == -1 )
            break;
        result.push_back(input);
    }
    return result;
}

Upvotes: 2

Related Questions