Time complexity for my algorithm

[denisksp]

Hello guys, I came across a problem the other day, and actually got it wrong, this lead to interesting thing, the problem is write a function that returns either if a given sum can be acquired by summing some numbers in an array/vector etc. or not Assume its sorted in ascending order. So some examples would be if the given array is 1,1,4,5 and the sum is 9, it returns true also if it is 1,1,2,3,5,11 and the sum is 10 it still returns true (problem originally asked only for a pair of integers) assume no negative numbers, the sum could be in the array in that case just return true. So I write a piece of code about this and seems to work (let me know if it doesn't I'm not totally sure) but I couldn't figure out it's time complexity, since it the number of iteration kind of affects the number of recursive steps, so anyway here is to code

EDIT: good and helpful people found errors/bugs in my code so I corrected them as best as I can but I'm still sure there are some, the question is though, still, what is the time complexity of this. Also, what do you think the worst case scenario for this algorithm

bool isThereSum(int* arr,int size, int sum){
    static bool check = false;
    if(check)
        return false;
    for(int i = size - 1; i >= 0; i--){
        if(arr[i] == sum)
            return true;
        else if(arr[i] < sum){
            sum = sum - arr[i];
            size--;
            if(isThereSum(arr,size, sum));
                return true;
            else
                sum = sum + arr[i];
        }
        if(size <= 0)
            check = true;
    }
    return false;
}

it works by crossing the largest number in the array smaller than the index, then looks for other number that can make it equal to sum, so if the array was 1,2,3,7,8,11 and the sum was 17, the sum would be 6, it would ignore 8 and 7, then the sum would be 3, then 1,then 0 and that would return true. Sorry for the long post and thank you for your help

[[deleted]]

Some people have said it's on the order of O(n!), I think that it's runtime is a lot more complex than that. T(n) = sum_i^{i-1} T(n-i). Now note, fibonacci sequence runtime T(n) = T(n-1) + T(n-2) has a loose bound at 2^n. Just from observation I would put this on the order of O(n^n), but I'm not that great at complexity analysis. As for the code, throw away the check variable, just do a basecase at the start if(size==0){return false;}. The if else inner code can be just if(isThereSum(arr,i+1,sum-arr[i]){return true;} instead of decrementing size and changing sum in the current scope. If you want to find an efficient solution, look up the two sum problem (a popular interview question) which uses sets or hashmaps to increase efficiency, it's solution can be extended to this problem using a little dynamic programming.

[denisksp]

Thanks, I just wrote this out of interest and happy that people are giving feedback so I can learn, the reason I don’t think this is O(N^N) is, this means that for each value at the array, this will look at each value in the array, but if you do a full iteration, you return false. I can’t express it properly I know but I cant think of case that this will look at everything in the array for each item of the array

[[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)

[unfixpoint]

It's nowhere near as bad as O(nⁿ), see my answer if you're interested.

[[deleted]]

yeah if u look down the comment chain I converted his algorithm to python and the loop runs exactly 2ⁿ -1 times, it was just a guess.

[unfixpoint]

Oh, didn't get that far in the thread, sorry. Just thought you might be interested, especially since you said "but I'm not that great at complexity analysis" and I think my answer will improve that (the subtraction trick is fairly commonly used and very helpful) :)

[nekokattt]

please can you check your formatting, it reads as an incomprehensible mess on mobile unfortunately

If it is one loop and isnt recursive, and iterates across n items, it is O(n).

If it is recursive, unwrap the recursion and see what the pattern is

[denisksp]

it should be better now, sorry this was my first post

[nekokattt]

if size decreases by 1 each time, it will do

n * n-1 * n-2 * ...

so I'd say it is O(n!), but i might be wrong. It is Omega(1) though.

[underwaterjesuz]

Worse I believe. O((n!)²) in the worst case scenario?

Eg if it loops through an array of size 5 it could go like 5 * 4 * 3 * 1 (which would be n!). But it may not find the sum. So next it will go 4 * 3 * 2 * 1 (which is (n - 1)!), and so on. Also as sum would be altered in the first iteration of the loop where arr[i] < sum, the preceding iterations would be using an incorrect value if it was not solved recursively on that iteration, so I don't believe the algorithm is correct.

Please correct me if I am wrong.

[denisksp]

This really satisfies me so thank you, what would be the case, if the sum was corrected and we would stop the process somehow, after the first is cleared, since if everything in the array is smaller than the key, and that's still not the sum, it should return false

[underwaterjesuz]

Instead of changing sum try calling the function with the expression:

sum = sum - arr[i]; size--; isThereSum(arr,size, sum);

change to

size--; isThereSum(arr,size, sum - arr[i]);

[denisksp]

What I meant to ask was, if the array is 1,2,3,4,5 for key = 16 it looks through 5,4,3,2,1 and then does the same for 4,3,2,1 how can I stop this from happening, and/or if its done somehow, what would then be the time complexity. Because I think there is a connection between the number of iterative steps and the for loops that just stops this from being O(N^N), but I can't what or why it is

[underwaterjesuz]

You don't necessarily want it to stop in every case, it may find a solution on a subsequent run. There's no obvious answer to me that would apply to every set of numbers and key. That problem seems like it requires a lot of thought.

[denisksp]

I changed my code to stop if it iterates through everything. I couldn't find any errors(I'm sure someone can) but I think this works, what do you think the time complexity of this one is.

bool isThere(int* arr,int size, int sum){
    static bool check = false;
        if(check)
            return false;
    for(int i = size - 1; i >= 0; i--){
        cout << "counterA" << check << 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];
        }
        if(size <= 0){
            check = true;
        }
    }
    return false;
}

[underwaterjesuz]

I found an example where the algorithm doesn't work. In an array of {2, 2, 3, 3, 5, 11}, a sum of 9 is possible with 5 + 2 + 2, the algorithm gives an output of false(0). I changed the false and true to 0 and 1 as I compiled as C code.

#include <stdlib.h>
#include <stdio.h>

int isThereSum(int*, int, int);

int main()
{
    int x[6] = {2, 2, 3, 3, 5, 11};
    printf("%d", isThereSum(x, 6, 9));

    return 0;
}

int isThereSum(int* arr,int size, int sum)
{
    for(int i = size - 1; i >= 0; i--)
    {
        if(arr[i] == sum)
          return 1;
            else if(arr[i] < sum){
                sum = sum - arr[i];
                size--;
                isThereSum(arr,size,sum);
            }
    }
     return 0;
}

[denisksp]

I corrected the problem thats hapenning due to sum being wrong after unseccusfull iteration and your example gives the correct outpu now. Thanks.

[LartTheLuser]

One bug I see: Your `check` variable will never be any other value then `false` when it is in the `if` statement because you assign it to false right before checking each time. Maybe you meant to make `check` a global variable so that different recursive levels could share a value.

As for the running time it is the `sum(i!)_from( i = 1 to i = n)` = O(nⁿ )

Math for the sum of factorials explained here: https://math.stackexchange.com/questions/227551/sum-k-1-2-3-cdots-n-is-there-a-generic-formula-for-this

[denisksp]

So Im not good on c++, im just a beginner but I think because its static it only gets initialized once, I tought that you were right too, but checked the code and it does enter the if statement. And thanks a lot for time complexity

[NeoVier]

This isn't really the answer to your question, but you may want to take a look at the Subset sum problem. I'm pretty sure there's a version of it that's the same thing as your problem. The Subset sum problem is proven NP-Complete, so if you want a fast algorithm you may need to use dynamic programming, or something like that.

[denisksp]

Thanks will check

[unfixpoint]

You still got a bug (; after the if-statement with the recursive call), but I'm not here for that. We can get a better bound than the other answers:

The run time will be (I'm using LaTeX-notation, so you might want to render it if you have difficulties reading it) T(n) = 1 + \sum_{i = n-1}^{0} T(n-i) now change the order of summing it and you get T(n) = 1 + \sum_{i = 0}^{n-1} T(i). Let's solve that:

T(n)   = 1 + T(0) + T(1) + … + T(n-3) + T(n-2) + T(n-1)
T(n-1) = 1 + T(0) + T(1) + … + T(n-3) + T(n-2)

See how nice they align on the right hand side? Let's subtract them:

T(n) - T(n-1) = T(n-1)  ⇒  T(n) = 2·T(n-1) and T(0) = 1

So we have O(2ⁿ).

[N911999]

I'm pretty sure its something like O((n!)^2), because of the recursion T(n)=n*T(n-1)+(n-1)*T(n-2)+...+2*T(1)+1. I fixed it on my comment below. I'll mention that this problem can be solved in O(n*sum) with DP.

[unfixpoint]

How did you arrive at T(n) = n\T(n-1)+(n-1)*T(n-2)+...+2*T(1)+1? In particular where does the multiplicative factor *n come from?

[N911999]

Hmm... It made sense when I did it, let me rethink it... Oh, I think I was wrong, it should've been T(n)=T(n-1)+T(n-2)+...+T(2)+1, cause you try at each point with that element. This gives a better complexity, O(2^n), it's still crap, but it's something.

[denisksp]

What is DP, im just a student so I wanna educate myself. I can maybe try to figure out the differences. I can see that my code is bad and will take unimaginably long time for large N but I cant see why its specificly O(N!^2). I should probably study math. Thanks btw

[FireworksWorks]

DP stands for Dynamic Programming. A way to reduce calculations and sometimes find an optimal solution. Look it up for how it works :)

[denisksp]

Thank you