question B... please describe the answer to the problem, not just solve it. e Ho

Question

question B... please describe the answer to the problem, not just solve it.

e Home q: Mail-ShahbazAhmedi x Secure https://outlook.office 365.com/owa/?realm mail.citytech.cuny edu&iexsvurl-18ll-cc-10338; Outlook Print MAT 254o Writing Assignment 1 For each of the items below, write a paragraph addressing each question. (a) Suppose that you step into an elevator at City Tech. There are 7 people in the elevator (including you) and 3 different buttons have been pushed. What is the largest number of people that you can guarantee will exit the elevator at one of the 3 floors selected? Explain. (b) Explain why 1+2+3+ (n-1)+nO(2). (c) Describe an algorithm, and write the pseudocode, that computes the Lucas numbers. (See problem 11 in section 8.2). e here to search

Explanation / Answer

b) 1 + 2+ 3+ + ...(n-1) + n = O(n2)

We know that Sum of N Natural numbers for 1 to N is

=> 1 + 2 + 3 + 4+ ....N-1 + N

=> N*(N+1)/2 [High School mathematics]

=> ( N2 + N ) / 2

Now we have the function => F(N) =  ( N2 + N ) / 2

We need to find Aymptotic notation for F(N)

=> We know that f(N) = O(g(N)) if there exists c and n0 such that c*g(N) >= f(N) for n>n0

we have F(N) =  ( N2 + N ) / 2 , Let g(n) = 2N2

We can easily say that c*g(n) >= f(n) with c = 2

Hence f(n) = O(g(N)) => O(N2)

Hence the time complexity is O(N2)


Thanks, let me know if there is any doubts/concern.

PLEASE UPVOTE if helpful. Comment if you need more clarification. I will respond

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.