이 의사 코드의 런타임 복잡성은 얼마나됩니까?

Question

의사 코드의 시간 복잡성을 이해하는 데 문제가 있습니다.

p=10; 
num=0; 
plimit=100000; 
    for (i = p; i<=plimit; i++) 
     for (j = 1; j<=i; j++) 
      num = num + 1; 

선형 검색이 될 것이라고 생각하지만 확인하고 싶습니다.

Answer 1

선형 시간이 아닙니다. 내부 루프는 각 반복에서 i가 증가함에 따라 증분 연산 비용을 가지므로 (n+1)*(n/2) 때문에 1 + 2 + 3 ... + n은 O (n)를 제공합니다.