Stack Overflow
Stack Overflow

Questions tagged [recurrence]

A recurrence relation is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the sequence is defined as a function of the preceding terms.

A recurrence relation is a set of equations that recursively define a sequence, with one or more initial terms given, and each subsequent term defined as a function of the preceding terms.

An example is the Fibonacci sequence, which can be defined as:
F(n) = F(n-1) + F(n-2), with F(0) = 1 and F(1) = 1.

Some simply defined recurrence relations can have very complex (chaotic) behaviours and they are a part of the field of mathematics known as nonlinear analysis.

Solving a recurrence relation means obtaining a closed-form solution: a non-recursive function expressed analytically in terms of a finite number of certain "well-known" functions.

Recurrence relations are of fundamental importance in analysis of algorithms. In computer science, recurrence usually emerges when we analyze the complexity of divide-and-conquer algorithms. If an algorithm is designed so that it will break a problem into smaller subproblems (divide and conquer), its running time is described by a recurrence relation.

For some typical recurrence relations, the asymptotic growth can be analyzed via the Master Theorem.

1040 questions
250
votes
17 answers

What's the best way to model recurring events in a calendar application?

I'm building a group calendar application that needs to support recurring events, but all the solutions I've come up with to handle these events seem like a hack. I can limit how far ahead one can look, and then generate all the events at once. Or I…
Clinton Dreisbach
  • 7,732
  • 6
  • 29
  • 27
39
votes
7 answers

Should I store dates or recurrence rules in my database when building a calendar app?

I am building a calendar website (ASP.NET MVC) application (think simple version of outlook) and i want to start supporting calendar events that are recurring (monthly, yearly, etc) right now I am storing actual dates in my but I wanted to figure…
leora
  • 188,729
  • 360
  • 878
  • 1,366
34
votes
6 answers

Determining the complexities given codes

Given a snipplet of code, how will you determine the complexities in general. I find myself getting very confused with Big O questions. For example, a very simple question: for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { …
Jiew Meng
  • 84,767
  • 185
  • 495
  • 805
26
votes
3 answers

n log n is O(n)?

I am trying to solve this recurrence T(n) = 3 T(n/2) + n lg n .. I have come to the solution that it belongs to masters theorem case 2 since n lg n is O(n^2) but after referring to the solution manual i noticed this solution that they have The…
Wael Awada
  • 1,506
  • 3
  • 18
  • 31
26
votes
5 answers

Modulus with negative numbers in C++

I have been writing a program for the following recurrence relation: An = 5An-1 - 2An-2 - An-3 + An-4 The output should be the Answer modulus 10^9 + 7.. I wrote a brute force approach for this one as follows... long long int t1=5, t2=9, t3=11,…
nitish712
  • 19,504
  • 5
  • 26
  • 34
20
votes
2 answers

how to write a recurrence relation for a given piece of code

In my algorithm and data structures class we were given a few recurrence relations either to solve or that we can see the complexity of an algorithm. At first, I thought that the mere purpose of these relations is to jot down the complexity of a…
Andrew Tobey
  • 915
  • 3
  • 10
  • 27
18
votes
3 answers

How can I compute the number of characters required to turn a string into a palindrome?

I recently found a contest problem that asks you to compute the minimum number of characters that must be inserted (anywhere) in a string to turn it into a palindrome. For example, given the string: "abcbd" we can turn it into a palindrome by…
IVlad
  • 43,099
  • 13
  • 111
  • 179
16
votes
2 answers

Relational Schema for Fowler's Temporal Expressions

Martin Fowler defines an elegant object model for the scheduling of recurring tasks here, which maps to OO code very nicely. Mapping this to a relational database schema for persistence, however, is tricky. Can anyone suggest a schema + SQL…
majelbstoat
  • 12,889
  • 4
  • 28
  • 26
15
votes
4 answers

Number of 1s in the two's complement binary representations of integers in a range

This problem is from the 2011 Codesprint (http://csfall11.interviewstreet.com/): One of the basics of Computer Science is knowing how numbers are represented in 2's complement. Imagine that you write down all numbers between A and B inclusive in 2's…
pdsouza
  • 621
  • 6
  • 9
15
votes
3 answers

Time complexity for a very complicated recursion code

I have some problem while trying to calculate time complexity for this code: function foo (int a): if a < 1: return 1 else: for i = 1 to 4: foo(a - 3) for i = 1 to 4: foo(a / 2) end…
Frzzy
  • 299
  • 1
  • 2
  • 16
15
votes
3 answers

Calculating the Recurrence Relation T(n)=T(n / log n) + Θ(1)

The question comes from Introduction to Algorithms 3rd Edition, P63, Problem 3-6, where it's introduced as Iterated functions. I rewrite it as follows: int T(int n){ for(int count = 0; n > 2 ; ++count) { n = n/log₂(n); } return…
Mike_Dog
  • 163
  • 7
13
votes
4 answers

Time complexity of the program using recurrence equation

I want to find out the time complexity of the program using recurrence equations. That is .. int f(int x) { if(x<1) return 1; else return f(x-1)+g(x); } int g(int x) { if(x<2) return 1; else return f(x-1)+g(x/2); } I write its recurrence…
siddstuff
  • 1,215
  • 4
  • 16
  • 37
13
votes
5 answers

How to determine the height of a recursion tree from a recurrence relation?

How does one go about determining the height of a recursion tree, built when dealing with recurrence run-times? How does it differ from determining the height of a regular tree? alt text…
Chris
  • 21,549
  • 25
  • 71
  • 99
12
votes
3 answers

General proof strategies to show correctness of recursive functions?

I'm wondering if there exists any rule/scheme of proceeding with proving algorithm correctness? For example we have a function $F$ defined on the natural numbers and defined below: function F(n,k) begin if k=0 then return 1 else if (n mod 2 = 0)…
xan
  • 1,053
  • 1
  • 10
  • 29
12
votes
1 answer

How to query recurrence rules in PostgreSQL?

I have a recurrence table that stores the iCalendar RFC 5545 Recurrence Rule string. Ex: FREQ=MONTHLY;INTERVAL=2 Does anyone know of any postgres functions similar to do the following? get_events_between(date,date) Where It would just query the…
terezzy
  • 243
  • 1
  • 3
  • 8
1
2 3
…
69 70