-1

What would be the complexity of this program in mathematical terms ? 

int main()
{
  int k = 1, n;
  cin >> n; //User Input

  while(k < n)
  {
     k = 7*k+5;
  }
}

This will be approached differently from the conventional "divide and conquer". The complexity might practically be O(1). But theoretically, it is not.The point is what would be the approach to solve such questions?

The term '5' in 'k = 7*k+5' is not as insignificant as it seems, for it is included in multiplication with each iteration. We will get the sequence - '1, 12, 89, 628, 4401, 30812' for n = 100000. That is the catch in the question. That is the actual problem I wanted to address. Kindly be considerate while voting on the question.

MadaZZ
  • 75
  • 8
  • 1
    Possible duplicate of [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – JJJ Apr 22 '18 at 11:59
  • It is not a duplicate. The link has conventional approaches to calculate the complexity by counting loops and by using divide and conquer approach for 'log n' situation. The link doesn't answer the question. – MadaZZ Apr 22 '18 at 12:17

2 Answers2

1

1) Time-complexity of k=7*k+5 is equal to O(1).

2) The loop iterates log(n).

Total operations is equal to O(logn). OR:

Bonje Fir
  • 787
  • 8
  • 25
  • The complexity might practically be O(1). But theoretically, it is not.The point is what would be the exact figure in terms of n for it is not defined. – MadaZZ Apr 22 '18 at 12:20
-1

In the equation k = 7*k+5, the term 5 is quite insignificant and can be ignored. SO we are getting a sequence which grows like:

1, 7, 49, 343, ....., n

Number of times this loop will run (r) is,

n = 1*(7^(r-1)) => log(7)n = (r-1) => r = log(7)n+1

So it will be a bit greater than O(1), and nearly equal to O(log(7)n)

Abhishek Keshri
  • 3,074
  • 14
  • 31