I've read a ton of questions on here already about finding the time complexity of different algorithms which I THINK I understand until I go to apply it to the outer loop of an algorithm which states:
for i=1 step i←n∗i while i < n^4 do
I can post the full algorithm if necessary but I'd prefer not to as it is for a piece of homework that i'd like to otherwise complete by myself if possible.
I just can't figure out what the complexity of that loop is. I think its just 4 unless n=1 but I am blank as to how to express that formally. Its that or im totally wrong anyway!
Is anyone able to help with this?
Translating your loop into C (just to make sure I understand your pseudo code):
for (i=1; i < n^4; i = i * n ) {
...
}
The key question is what is i after xth iteration? Answer: i^x (you can prove by induction). So when x is 4, then i is n^4 and the loop exits. So it runs in 4 iterations and is constant time.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments