0 Replies - 864 Views - Last Post: 07 January 2011 - 11:15 AM

#1 MathiasVP  Icon User is offline

  • D.I.C Head

Reputation: 27
  • View blog
  • Posts: 154
  • Joined: 08-August 10

Help on calculating O(n) for my subroutines

Posted 07 January 2011 - 11:15 AM

Hello people!
I recently read the Big O notation tutorial here on DIC and found it quite interesting, and now I'm writing a report in my mechatronics class. I'm normally only coding in C++, but our teacher only accepts assembly code so I'm not very experienced in this language.

I decided to compare 2 delay subroutines written in assembly by calculating the big O notation for each function, but I'm having some problems.
Here are my 2 subroutines:
wait     				
	movlw   d'255'	    
	movwf   count1

wait1	
	movlw   d'255'		
	movwf   count2		

wait2	
	movlw   d'255'
	movwf   count3
	
wait3
	movlw	d'255'
	movwf	count4		
	
wait4
	decfsz	count4,1
		goto wait4
	decfsz  count3,1	
		goto wait3			
	decfsz  count2,1		
		goto wait2			
	decfsz  count1,1		
		goto wait1


return



Wait
	movlw   d'255'
	movwf	count1
d1	decfsz	count1
		goto d21
	return

d21	movwf	count2
d22	decfsz	count2
		goto d31
	goto	d1
	
d31	movwf	count3
d32	decfsz	count3
		goto d41
	goto	d22
	
d41	movwf	count4
d42	decfsz	count4
		goto d42
	goto	d32



The first subroutine is the one that our teacher gave us, and I'm not quite sure of the big O notation of that one, but first thought was O(n^4).
The last one is my own version of a delay subroutine where the loop nesting is a bit clearer, which is why I'm pretty sure this is O(n^4).

So are these assumptions correct?

Thanks in advance!

Is This A Good Question/Topic? 0
  • +

Page 1 of 1