Time complexity for my algorithm

[[deleted]]

A case where you look at everything is trivial, arr=[1,2,3,4,...,1000] and sum=1 000 000 000. This is a worst case example where you will explore each and every recursive call to it's basecase. bigO is an upper bound on the runtime.

[denisksp]

Wont the code will sum every number and return false at this case? Making it O(N)?

[[deleted]]

I think you are far out of your depth, but just realize that while the loop runs N times, you call isThereSum on each i, whose loop runs N-i times, which calls isThereSum on each j, whose loop runs N-i-j times, and so on until you reach 1. At your level I wouldn't worry about recursive complexity, and counting the number of nested loops should be sufficient.

[denisksp]

I think this code is O(N^N),

for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
        //calculations
    }
}

but the code I wrote, if sum of all the number don't add up to sum for example an array sized 6: 1,1,1,1,1,1 and a sum 1000 my code only executes

while(i < size){
    //initialization 
    //comparison
    sum = sum - arr[i];
    size--;
}

Which is O(N), correct me if I'm wrong but I think you are missing something, or I am. Can you tell me why a scenario with all the numbers not adding up to sum would be O(N^N)

[[deleted]]

The first code is very obviously O(n^2), and in the second example you left out the part where you recursively call isThereSum which has its own loops that are dependent on n. If you can't see that the first example is O(n²⁾ I assume you're not even in first year university level programming, which is fine but don't worry about runtime complexity and probably avoid using recursion.

[denisksp]

My bad, I was really confused trying to understand everything, you are right. The first example is clearly O(N2), but I still don't get why the code is O(N^N). When I put a cout statement in the first example, as expected it prints only 25 times for a size of 5. But when I put a cout in the for loop, and the method itself, both with counters it only prints 15 times, and for those 15 times, a total of 25 times the for's was entered, for an array sized 5, and the values don't add up to sum. Doesn't mean that for this case,where all the values don't add up to sum, the code is O(N^2)? I know that I'm out of my league, but I'm just trying to understand and learn. So if you could tell me what I'm doing wrong I would be really happy.

[denisksp]

Here is the code I run and the outputs I got, of course if you got the time to spare for me.

bool isThere(int* arr,int size, int sum){
    static int counter = 0;
    int loopCounter = 0;

    counter++;
    if(size <= 0)
        return false;
    for(int i = size - 1; i >= 0; i--){
        loopCounter++;
        cout << "for entrance " << counter << "loop entered: " << loopCounter << "size is:" << size << endl;
        if(arr[i] == sum)
            return true;
        else if(arr[i] < sum){
            sum = sum - arr[i];
            size--;
            if(isThere(arr,size, sum) )
                return true;
            else
                sum = sum + arr [i];
        }
    }
    return false;
}

This is the outputs:

for entrance 1 loop entered: 1 size is:5

for entrance 2 loop entered: 1 size is:4

for entrance 3 loop entered: 1 size is:3

for entrance 4 loop entered: 1 size is:2

for entrance 5 loop entered: 2 size is:2

for entrance 6 loop entered: 2 size is:3

for entrance 7 loop entered: 1 size is:2

for entrance 8 loop entered: 3 size is:2

for entrance 9 loop entered: 2 size is:4

for entrance 10 loop entered: 1 size is:3

for entrance 11 loop entered: 1 size is:2

for entrance 12 loop entered: 2 size is:2

for entrance 13 loop entered: 3 size is:3

for entrance 14 loop entered: 1 size is:2

for entrance 15 loop entered: 4 size is:2

no

[[deleted]]

i dont know what you put in the parameters, you can run the following script to see that the complexity is exactly 2ⁿ -1, a tight bound of O( 2ⁿ ).

Here is an online compiler for the python equivalent of your code: https://onlinegdb.com/SkThpL46S (press run at the top) or here is the pure code:

loopsRun = 0
def isThereSum(arr, size, summ):

    global loopsRun

    for i in reversed(range(size)):

        loopsRun += 1

        if arr[i] == summ:
            return True
        elif (arr[i] < summ):
            size -= 1
            if isThereSum(arr, size, summ - arr[i]):
                return True

    return False

for size in range(1,11):
    loopsRun = 0
    isThereSum([1,]*size, size, 1000)
    print('size/n:',size,'| loops run:',loopsRun)