-1

I solved a given recurrence solution to determine f(n) and finally got f(n)=(1-(1-k)^(n+1)). Now, what can the possible time complexity for f(n)=(1-(1-k)^(n+1))?

Michaylor Riya
  • 23
  • 5
  • This is unclear. Are you asking about the time complexity to **compute** `f(n)` using that formula? If yes, it depends on the algorithm (i.e. the code) that you use to compute the value. (A mathematical formula doesn't have a time complexity. It is just a bunch of symbols.) – Stephen C Feb 13 '22 at 08:06
  • Then what could be the efficient algorithm for solving it? – Michaylor Riya Feb 13 '22 at 08:10
  • On the other hand ... if `f(n)` is a formula for the time taken to compute something ... there is some doubt as to whether it is meaningful. – Stephen C Feb 13 '22 at 08:11
  • *"Then what could be the efficient algorithm for solving it?"* - That's a different question to what you asked! And the answer depends on 1) the range for `k` and `n`, 2) whether `k` is an integer or real (or complex) number, and 3) the accuracy you require for the computed value. – Stephen C Feb 13 '22 at 08:12
  • The mother recurrence relation was : f(n)= (1−f(n-1))∗k+f(n-1). Here, "n" is the size of input and k is constant ranging [0,1]. – Michaylor Riya Feb 13 '22 at 08:14
  • Well in that case you can compute `f(n)` with `double` and `Math.pow`. The complexity will be `O(1)` I think. – Stephen C Feb 13 '22 at 08:43
  • 2
    Time complexity is relevant for algorithms. Where is the algorithm? – trincot Feb 13 '22 at 10:41
  • @trincot - Based on the information provided, the algorithm to compute `f(n, k)` is (in Java) `double f(int n, double k) { return 1 - Math.pow(1 - k, n + 1); }`. That is `O(1)`. – Stephen C Feb 13 '22 at 13:23
  • @StephenC, that is not in the question. I would like feedback from the Asker. – trincot Feb 13 '22 at 13:28
  • The pseudo-code in java manifested by @StephenC is what the algorithm is. And my question was how to determine the TC for executing those bunch of codes in order to calculate f(n,k). – Michaylor Riya Feb 14 '22 at 07:29
  • Solving recurrence relations for time complexity: https://users.cs.duke.edu/~ola/ap/recurrence.html Some seem not to understand that it is not about calculating f, but f is the time complexity, which has to be stated as O notation. – Sebastian Feb 14 '22 at 09:31

1 Answers1

-1

(Turning the comments into an answer)

It transpires from the Michaylor's clarifying comments, that this Question really is about the complexity of computing the formula

f(n, k) = 1 - (1 - k)(n + 1)

where "n" is a positive integer and "k" is a real number in the range 0 to 1.

First of all, it should be stated that formulae don't have execution times as they are not algorithms. However, since there are no particular requirements for the precision of the result, we can compute it using the following Java code.

double f(int n, double k) { 
    return 1 - Math.pow(1 - k, n + 1); 
}

where Math is the standard java.lang.Math class. The computational complexity of Math.pow in modern Java implementations is O(1) (see Java Math.pow(a,b) time complexity) so the complexity of the algorithm (expressed in Java) is also O(1).

Notes:

  1. It is not a given that the implementation of the equivalent of pow(a, b) will be O(1) in all programming languages' runtime libraries.

  2. If better precision than double provides was required, the algorithm would need to use BigDecimal or equivalent. It wouldn't necessarily be O(1).

  3. To illustrate the distinction between formulae and algorithms, if we were to replace Math.pow(1 - k, n + 1) with a naive for loop, that version would have a complexity of O(n)!

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
  • The comments state the opposite: n is the input size, the question is about O(f(n)) – Sebastian Feb 14 '22 at 08:09
  • @Sebastian - Please interpret this for me: " The pseudo-code in java manifested by StephenC **is what the algorithm is**. And my question was how to determine the TC for executing **those bunch of codes** in order to calculate f(n,k). " - Michaylor Riya 1 – Stephen C Feb 14 '22 at 08:44