• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Problem regarding time complexity

 
Ranch Hand
Posts: 692
Eclipse IDE Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I was reading a book which tellls that the outer loops time complexity is O(n-m) whereas for inner loop the books gives explanation as

" The inner while
loop goes around at most m times, and potentially far less when the pattern match
fails. This, plus two other statements, lies within the outer for loop. The outer loop
goes around at most n−m times, since no complete alignment is possible once we
get too far to the right of the text. The time complexity of nested loops multiplies,
so this gives a worst-case running time of O((n − m)(m + 2)). "


i didn't understand for what reason the time complexity of inner loop is O(m+2) instead of O(m) ?please help thanks


 
Greenhorn
Posts: 3
Monad C++ Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Algorithm books like to be confusing. The for loop in your example will run n-m+1 times so that becomes the complexity and it'll be multiplied by the complexity of the inner loop. I'll try to demonstrate.

I'll use an example of two while loops because basically a while loop comes out to be the same thing as a for loop in time analysis.

Basically the time analysis on a while loop amounts to

twhile being the time of the while loop
tbody being the time of the body of the while loop
tcond being the time of the conditional of the while loop
"r" being how many times the body is to be run

The reason tcond is there at the end is because it will be ran again and become false at the end of loop.

So if you have loops inside of loops for instance:


Then we'll call the first while loop T1while and the second while loop T2while so T1 become


 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic