13 Replies - 1021 Views - Last Post: 07 May 2016 - 12:33 PM

#1 novakasss  Icon User is offline

  • D.I.C Regular

Reputation: 4
  • View blog
  • Posts: 458
  • Joined: 11-July 12

Complexity of an algorithm

Posted 07 May 2016 - 09:28 AM

I have this code snippet:
  1.  Dim C(n) As Integer
  2.  AA(C, 1, n)
  3.  For j As Integer = 1 To n
  4.      For i As Integer = j To j + 5
  5.        print C(i) + i
  6.      Next
  7.  Next

    Sub AA(C As Integer(), m As Integer, n As Integer)
        Dim p As Integer = (n  m + 1) / 3
        If p > 1 Then
            For i As Integer = 1 To 4
              AA(C, m , m + p)
            Next
            For i As Integer = m To n
                    C(i) = C(i) + 1
            Next
        End If
    End Sub


I need to find the complexity of lines 1-7. But first I have to find out how many times each line will be executed. What I think:
  1.  Dim C(n) As Integer // 1
  2.  AA(C, 1, n) // 1
  3.  For j As Integer = 1 To n // n
  4.      For i As Integer = j To j + 5 // n-1
  5.        print C(i) + i // n-2
  6.      Next
  7.  Next

    Sub AA(C As Integer(), m As Integer, n As Integer)
        Dim p As Integer = (n  m + 1) / 3 // 1
        If p > 1 Then // ?
            For i As Integer = 1 To 4 // n
              AA(C, m , m + p) // n-1
            Next
            For i As Integer = m To n // n
                    C(i) = C(i) + 1 // n-1
            Next
        End If
    End Sub


How to determine how many times that if statement will be executed if I don't know what is the value of n?

Is This A Good Question/Topic? 0
  • +

Replies To: Complexity of an algorithm

#2 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 13396
  • View blog
  • Posts: 53,465
  • Joined: 12-June 08

Re: Complexity of an algorithm

Posted 07 May 2016 - 10:23 AM

Have you read up on big-o notation?
http://www.dreaminco...big-o-notation/
Was This Post Helpful? 1
  • +
  • -

#3 novakasss  Icon User is offline

  • D.I.C Regular

Reputation: 4
  • View blog
  • Posts: 458
  • Joined: 11-July 12

Re: Complexity of an algorithm

Posted 07 May 2016 - 10:35 AM

View Postmodi123_1, on 07 May 2016 - 10:23 AM, said:

Have you read up on big-o notation?
http://www.dreaminco...big-o-notation/

But none of those examples have a case where an if statement appears or recursion.

EDIT: Sorry, I found one post about if.

This post has been edited by novakasss: 07 May 2016 - 10:41 AM

Was This Post Helpful? 0
  • +
  • -

#4 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 13396
  • View blog
  • Posts: 53,465
  • Joined: 12-June 08

Re: Complexity of an algorithm

Posted 07 May 2016 - 10:42 AM

That shouldn't prevent you from searching:

"big o if statement"
http://pages.cs.wisc...COMPLEXITY.html
... or thinking about time complexity for an if statement versus any other single line, non loop, statement.. which is 'nil' in the big scope of things.

You can similarly look up "big o recursive"
https://users.cs.duk...recurrence.html
http://www.usna.edu/...s/class07.shtml
Was This Post Helpful? 2
  • +
  • -

#5 novakasss  Icon User is offline

  • D.I.C Regular

Reputation: 4
  • View blog
  • Posts: 458
  • Joined: 11-July 12

Re: Complexity of an algorithm

Posted 07 May 2016 - 11:10 AM

If I would like to use a Master Method, is this equation is good?

T(n) = T(n/4) + 1

n/4 because in each recursive function there are 4 other calls. + 1 because each recursive function has a complexity of O(1). Is that right?

This post has been edited by andrewsw: 07 May 2016 - 11:37 AM
Reason for edit:: Removed previous quote, just press REPLY

Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,117
  • Joined: 27-December 08

Re: Complexity of an algorithm

Posted 07 May 2016 - 11:35 AM

The Master Theorem doesn't really apply here; at least, not the way you set it up. T(n/4) with indicates that a recursive call only considers a problem of size n/4. The coefficient of T(n/4) indicates how many recursive calls are made, where each of these calls considers problems of size n/4.

Let's consider your recursive function line-by-line.

  Sub AA(C As Integer(), m As Integer, n As Integer)
      Dim p As Integer = (n – m + 1) / 3 // 1
      If p > 1 Then // ?
          For i As Integer = 1 To 4 // n
            AA(C, m , m + p) // n-1
          Next
          For i As Integer = m To n // n
                  C(i) = C(i) + 1 // n-1
          Next
      End If
  End Sub



Observe the base case is when p == 1. Your first line where you declare and assign p takes O(1) time, which will be executed in each invocation of the method. So your base case takes O(1) steps.

If p > 1, then we have two components: the recursive calls and modifying your array. The recursive call AA(C, m, m+p) is equivalent to AA(C, m, 2m/3 + (n + 1)/3). You have four of these calls. Then the for loop takes n - m steps.

So T(m, n) = 4T(m, 2m/3 + (n+1)/3) + n - m + O(1).

Now at line 2, you invoke AA(C, 1, n). So you can take So T(m, n) = 4T(m, 2m/3 + (n+1)/3) + n - m + O(1) and set m = 1. This should make it easier to solve.
1.  Dim C(n) As Integer
2.  AA(C, 1, n)
3.  For j As Integer = 1 To n
4.      For i As Integer = j To j + 5
5.        print C(i) + i
6.      Next
7.  Next


This post has been edited by macosxnerd101: 07 May 2016 - 11:53 AM
Reason for edit:: Algebra error

Was This Post Helpful? 1
  • +
  • -

#7 novakasss  Icon User is offline

  • D.I.C Regular

Reputation: 4
  • View blog
  • Posts: 458
  • Joined: 11-July 12

Re: Complexity of an algorithm

Posted 07 May 2016 - 11:52 AM

I read somewhere that from this:
T(m, n) = 4T(m, (n+1)/3) + n - m + O(1)


I can instead write:
T(m, n) = 4T(m, (n+1)/3) + O(n)

? Because n is a biggest of all three?

And then:
log 4 (base 3) comparing to n is MORE, so T(n) = O(log 4 base 3) ?

I actually have never did this before with two variables n, m. Wikipedia also describes only with one var. Is it the same procedure?
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,117
  • Joined: 27-December 08

Re: Complexity of an algorithm

Posted 07 May 2016 - 11:57 AM

I made a minor algebra error. Note that T(m, n) should be: So T(m, n) = 4T(m, 2m/3 + (n+1)/3) + n - m + O(1). Yes, since m <= n, you can write n - m + O(1) as O(n).

Quote

And then:
log 4 (base 3) comparing to n is MORE, so T(n) = O(log 4 base 3) ?

log(4) is a constant, regardless of the base. You are trying to apply the Master Theorem but haven't justified if you can use it.

Quote

I actually have never did this before with two variables n, m. Wikipedia also describes only with one var. Is it the same procedure?

From my last post:

Quote

Now at line 2, you invoke AA(C, 1, n). So you can take So T(m, n) = 4T(m, 2m/3 + (n+1)/3) + n - m + O(1) and set m = 1. This should make it easier to solve.


Substitute m = 1 into T(m, n). Then you have a function in one variable.
Was This Post Helpful? 1
  • +
  • -

#9 novakasss  Icon User is offline

  • D.I.C Regular

Reputation: 4
  • View blog
  • Posts: 458
  • Joined: 11-July 12

Re: Complexity of an algorithm

Posted 07 May 2016 - 12:10 PM

So I will get:
T(n) = 4T( 2/3 + (n+1)/3 ) + O(n) ?
Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,117
  • Joined: 27-December 08

Re: Complexity of an algorithm

Posted 07 May 2016 - 12:12 PM

Yes.
Was This Post Helpful? 0
  • +
  • -

#11 novakasss  Icon User is offline

  • D.I.C Regular

Reputation: 4
  • View blog
  • Posts: 458
  • Joined: 11-July 12

Re: Complexity of an algorithm

Posted 07 May 2016 - 12:13 PM

Can I solve this with Master Method? I see that
a = 4
b = 3

but where to put those 2/3 and n+1
Was This Post Helpful? 0
  • +
  • -

#12 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,117
  • Joined: 27-December 08

Re: Complexity of an algorithm

Posted 07 May 2016 - 12:14 PM

What does the Master Theorem say? What are the conditions you need to satisfy to apply it?
Was This Post Helpful? 0
  • +
  • -

#13 novakasss  Icon User is offline

  • D.I.C Regular

Reputation: 4
  • View blog
  • Posts: 458
  • Joined: 11-July 12

Re: Complexity of an algorithm

Posted 07 May 2016 - 12:22 PM

to have a form T(n) = aT(n/B) + f(n) ?

I only know this and a concept of Recursive three.
Was This Post Helpful? 0
  • +
  • -

#14 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,117
  • Joined: 27-December 08

Re: Complexity of an algorithm

Posted 07 May 2016 - 12:33 PM

That's not all the Master Theorem states, but that is a necessary condition. So clearly, you cannot apply the Master Theorem. You can try using the recursion tree approach. I would encourage you to take some time and really play around with it.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1