Click here to Skip to main content
15,881,281 members
Search within:


I need a little help in solving time and space complexity of the algorithms
Please Sign up or sign in to vote.
1.00/5 (2 votes)
Hello All,

Thanks for participation and your precious suggestions, I have done some of the algorithms but I stuck in these two, Could you (experts) find time complexity for the following two algorithm with explanation (steps) so I can solve the rest in future.

Note: I am not been paid nor given task but I wan to solve these algorithm posted in shape of paper on pdfcoffee.com


Algorithm which just sums up for no apparent reason

π‘π‘Ÿπ‘œπ‘π‘’π‘‘π‘’π‘Ÿπ‘’π‘†π‘œπ‘šπ‘’π΄π‘™π‘”3(𝑛)
π‘ π‘’π‘š = 0
π‘“π‘œπ‘Ÿ 𝑖 = 1 π‘‘π‘œ βˆšπ‘› π‘‘π‘œ
π‘ π‘’π‘š = π‘ π‘’π‘š + 𝑖
𝑒𝑛𝑑 π‘“π‘œπ‘Ÿ
π‘“π‘œπ‘Ÿ 𝑖 = 1 π‘‘π‘œ βˆšπ‘› π‘‘π‘œ
2
π‘ π‘’π‘š = π‘ π‘’π‘š + 𝑖
𝑒𝑛𝑑 π‘“π‘œπ‘Ÿ
π‘“π‘œπ‘Ÿ 𝑖 = 1 π‘‘π‘œ 10 π‘‘π‘œ
π‘ π‘’π‘š = π‘ π‘’π‘š + 𝑖
𝑒𝑛𝑑 π‘“π‘œπ‘Ÿ
𝑒𝑛𝑑 π‘π‘Ÿπ‘œπ‘π‘’π‘‘π‘’π‘Ÿπ‘’


Algorithm which just sums up for no apparent reason

π‘π‘Ÿπ‘œπ‘π‘’π‘‘π‘’π‘Ÿπ‘’π‘†π‘œπ‘šπ‘’π΄π‘™π‘”4(𝑛)
π‘ π‘’π‘š = 0
π‘“π‘œπ‘Ÿ 𝑖 = 1 π‘‘π‘œ βˆšπ‘› π‘‘π‘œ
π‘“π‘œπ‘Ÿ 𝑗 = 1 π‘‘π‘œ 5 π‘‘π‘œ
π‘ π‘’π‘š = π‘ π‘’π‘š + 𝑖 βˆ— 𝑗
𝑒𝑛𝑑 π‘“π‘œπ‘Ÿ
𝑒𝑛𝑑 π‘“π‘œπ‘Ÿ
𝑒𝑛𝑑 π‘π‘Ÿπ‘œπ‘π‘’π‘‘π‘’π‘Ÿπ‘’



What I have tried:

I have enthusiasm to solve paper posted on pdfcoffee.com
Posted
Updated 25-Apr-21 9:53am
v2
Add a Solution

3 solutions

I suspect an error in
C#
𝑝𝑟𝑜𝑐𝑒𝑑𝑢𝑟𝑒 𝑀𝑎𝑡𝐸𝑙𝑒𝑚𝑒𝑛𝑡𝑠𝑆𝑢𝑚(𝐴[0 … 𝑛 βˆ’ 1,0, … . 𝑚 βˆ’ 1])
𝑠𝑢𝑚 = 0;
𝑓𝑜𝑟 𝑖 = 0 𝑡𝑜 𝑛 βˆ’ 1 𝑑𝑜
𝑓𝑜𝑟 𝑗  = 0 𝑡𝑜 𝑚 βˆ’ 1 𝑑𝑜
𝑠𝑢𝑚  = 𝑠𝑢𝑚 + 𝐴[𝑖] // I would have expected A[i,j]
𝑒𝑛𝑑 𝑓𝑜𝑟
𝑒𝑛𝑑 𝑓𝑜𝑟
𝑟𝑒𝑡𝑢𝑟𝑛 𝑠𝑢𝑚
𝑒𝑛𝑑 𝑝𝑟𝑜𝑐𝑒𝑑𝑢𝑟𝑒

, but it does not change the result of complexity.
Quote:
Algorithm 1: Algorithm to find the sum of all elements of a matrix of size 𝑛 βˆ— π‘š

Without looking at code, how many operations do you need to do to sum all elements of a matrix n*m ?
If matrix is 2*2, 3*3, 5*6, 10*10 ?
Now look at the code and try to get how many times each line is executed.
Quote:
I have been given a task so I am not able to track the solution therefore, I approach this forum.

It is impossible to come up with nothing, unless you skipped the course.
If you are just not sure of your solutions, show it and tell us.

[Update]
Quote:
I have enthusiasm to solve paper posted on pdfcoffee.com

No, you are enthusiast to have us solving the problem and then post our solution as being your work.
You'd better learn how to solve the problem by yourself.
 
Share this answer
 
Posted
Updated 25-Apr-21 13:50pm
v2
Comments
CPallini 20-Apr-21 7:07am    
My 5.
Patrice T 20-Apr-21 7:20am    
Thank you
Consider algorithm 1: there is a statement executed (m*n) times, namely
𝑠𝑢𝑚  = 𝑠𝑢𝑚 + 𝐴[𝑖]
Other statements are executed once (e.g. π‘ π‘’π‘š = 0;), so, for big values of n and m, their contribution is negligible.

Therefore you may write the time complexity this way:
O(n*m)


Now, applying a similar reasoning to space complexity and solving for the other algorithms is up to you.
 
Share this answer
 
Posted
Updated 19-Apr-21 22:15pm
v2
Comments
Patrice T 20-Apr-21 6:57am    
+5
CPallini 20-Apr-21 7:07am    
Thank you!
We are more than willing to help those that are stuck: but that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.

So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

Just saying "I need a little help" and then posting your entire homework without showing you have tried anything isn't going to get you anywhere.

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]
 
Share this answer
 
Posted
Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
Top Experts
Last 24hrsThis month
Related Questions
What is time and space complexity of this code?
Low time complexity in linked list deletion?
Help solving Knapsack Algorithm
Finding complexity of algo
Lnked lists: how to minimize time and space complexity in a concrete case
Solve this algorithm
I need help to build a fair meeting assignment algorithm between agents.
Complexity of algorithms
how find Time Complexity and Space Complexity of a Program
Minimum time complexity in linked list deletion

Advertise
Privacy
Cookies
Terms of Use
Last Updated 25 Apr 2021
Layout: fixed | fluid
Copyright © CodeProject, 1999-2024
All Rights Reserved.

Web04 2.8:2024-04-02:1

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900