CODEWITHSUNDEEP
algorithmtime-complexityanalysis
Jamie
Jamie

Reputation: 3

Time complexity T(n) for an algorithm that depends on 2 inputs

Normally when analyzing the running time of an algorithm i am dealing with a single input that affects the running time. I'm trying to understand how to represent T(n) when there are 2 or more inputs that affect the running time.

For example in linear search in the worse case:

function LinearSearch(arr, N, x)
    for (i = 0; i < N; i++)        ---> C1*N + C2
        if arr[i] = x              ---> C3*N
            return true            

    return false                   ---> C4

T(n) = (C1 + C3)*N + (C2 + C4) = CN + C

so T(n) is linear with respect to N.

Now say there was an another algorithm that took in inputs X and Y and i did a similar analysis and found the cost in the worst case to be:

T(n) = CX + C

and the best case to be:

T(n) = CY + C

My question is, is it correct to represent the running time like this? Given that there are two different inputs that affect the running time in different cases.

I've not managed to find much information online or in text books but i've been thinking about whether the n in T(n) represents all the inputs, or could it be represented like so:

T(X) = CX + C

T(Y) = CY + C

I've also seen an algorithm in a research paper described similarly to:

T(n, m) = some expression

Any help would be greatly appreciated.

Thanks

EDIT: An example of an algorithm where the time complexity depends on two inputs could be radix sort.

I understand that radix sort is often represented as O(n*k) where n is the number of elements to be sorted and k is the number of digits of the max value.

Ignoring the the exact details of T(n), how might this be represented?

Upvotes: 0

Views: 1486

Answers (1)

Mo B.
Mo B.

Reputation: 5827

If the complexity of the algorithm depends on a single parameter and you want to call that parameter X, the time complexity will also be dependent on X and not on n (what is n?): e.g. T(X) = X^2.

If the complexity of the algorithm depends on parameters n1, n2, ..., nk (and the parameters are mutually independent), then the time complexity will be a function in k parameters, T(n1, ..., nk).

For example, an algorithm that takes two strings of lengths x and y and prints them would have time complexity T(x,y) = O(x + y).

Upvotes: 1

Related Questions