0

What is the running time complexity of following fucntion.

public void funtion(int n){
       int i=1,s=1;
       while(s<=n){
       i++;
       s=s+i;
       System.out.println("*");
    }
    }
Arjun Tirumalasetty
  • 1
  • 2
  • Welcome to stack overflow :) I've duped your question with a general one on how to find time complexities for functions. A good question shows what you've tried already and a specific place where you're stuck. Since your question doesn't contain this information, it's hard to know what help to provide other than general hints for solving this (presumably homework) problem. See also: https://meta.stackoverflow.com/questions/334822/how-do-i-ask-and-answer-homework-questions – Paul Hankin Dec 12 '21 at 09:04

1 Answers1

0

At step k, S=sum (i for i in 1,K)=K(K+1)/2

So you will make K loops with k such that k(k+1)/2=n

k**2+K-2n=0 the positive root is K = (-1+sqrt(1+8n))/2 = sqrt(1/4+2n)-1/2

Jean Valj
  • 119
  • 4